Revert r332907 "[GlobalISel] Improving InstructionSelect's performance by reducing MatchTable..."

There is a compile time error I didn't see locally, investigating now.

llvm-svn: 332912

1 files changed, 305 insertions, 560 deletions

diff --git a/llvm/utils/TableGen/GlobalISelEmitter.cpp b/llvm/utils/TableGen/GlobalISelEmitter.cpp
index c852fb36e17..1237f8c4e16 100644
--- a/llvm/utils/TableGen/GlobalISelEmitter.cpp
+++ b/llvm/utils/TableGen/GlobalISelEmitter.cpp
@@ -100,7 +100,6 @@ private:
   LLT Ty;
 
 public:
-  LLTCodeGen() = default;
   LLTCodeGen(const LLT &Ty) : Ty(Ty) {}
 
   std::string getCxxEnumValue() const {
@@ -402,34 +401,13 @@ 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,
-                   int64_t RawValue = std::numeric_limits<int64_t>::min())
+                   unsigned NumElements, unsigned Flags)
       : LabelID(LabelID_.hasValue() ? LabelID_.getValue() : ~0u),
-        EmitStr(EmitStr), NumElements(NumElements), Flags(Flags),
-        RawValue(RawValue) {
-
+        EmitStr(EmitStr), NumElements(NumElements), Flags(Flags) {
     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;
@@ -475,20 +453,11 @@ 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);
@@ -617,12 +586,8 @@ class RuleMatcher;
 class Matcher {
 public:
   virtual ~Matcher() = default;
-  virtual void optimize() {}
   virtual void emit(MatchTable &Table) = 0;
-
-  virtual bool hasFirstCondition() const = 0;
-  virtual const PredicateMatcher &getFirstCondition() const = 0;
-  virtual std::unique_ptr<PredicateMatcher> popFirstCondition() = 0;
+  virtual std::unique_ptr<PredicateMatcher> forgetFirstCondition() = 0;
 };
 
 MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
@@ -634,75 +599,34 @@ MatchTable MatchTable::buildTable(ArrayRef<Matcher *> Rules,
   return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
 }
 
-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;
+class GroupMatcher : public Matcher {
+  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions;
+  SmallVector<Matcher *, 8> Rules;
 
 public:
-  /// 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 addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) {
+    Conditions.emplace_back(std::move(Predicate));
   }
-  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;
+  void addRule(Matcher &Rule) { Rules.push_back(&Rule); }
+  const std::unique_ptr<PredicateMatcher> &conditions_back() const {
+    return Conditions.back();
   }
-  const PredicateMatcher &getFirstCondition() const override {
-    assert(!Conditions.empty() &&
-           "Trying to get a condition from a condition-less group");
-    return *Conditions.front();
+  bool lastConditionMatches(const PredicateMatcher &Predicate) const;
+  bool conditions_empty() const { return Conditions.empty(); }
+  void clear() {
+    Conditions.clear();
+    Rules.clear();
   }
-  bool hasFirstCondition() const override { return !Conditions.empty(); }
+  void emit(MatchTable &Table) override;
 
-private:
-  /// See if a candidate matcher could be added to this group solely by
-  /// analyzing its first condition.
-  bool candidateConditionMatches(const PredicateMatcher &Predicate) const;
+  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");
+  }
 };
 
 /// Generates code to check that a match rule matches.
@@ -716,19 +640,20 @@ 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.
-  using MatchersTy = std::vector<std::unique_ptr<InstructionMatcher>> ;
-  MatchersTy Matchers;
+  std::vector<std::unique_ptr<InstructionMatcher>> Matchers;
 
   /// A list of actions that need to be taken when all predicates in this rule
   /// have succeeded.
   ActionList Actions;
 
-  using DefinedInsnVariablesMap = std::map<InstructionMatcher *, unsigned>;
+  using DefinedInsnVariablesMap =
+      std::map<const InstructionMatcher *, unsigned>;
 
-  /// A map of instruction matchers to the local variables
+  /// A map of instruction matchers to the local variables created by
+  /// emitCaptureOpcodes().
   DefinedInsnVariablesMap InsnVariableIDs;
 
-  using MutatableInsnSet = SmallPtrSet<InstructionMatcher *, 4>;
+  using MutatableInsnSet = SmallPtrSet<const InstructionMatcher *, 4>;
 
   // The set of instruction matchers that have not yet been claimed for mutation
   // by a BuildMI.
@@ -738,7 +663,7 @@ protected:
   /// the renderers.
   StringMap<OperandMatcher *> DefinedOperands;
 
-  /// ID for the next instruction variable defined with implicitlyDefineInsnVar()
+  /// ID for the next instruction variable defined with defineInsnVar()
   unsigned NextInsnVarID;
 
   /// ID for the next output instruction allocated with allocateOutputInsnID()
@@ -748,7 +673,6 @@ protected:
   unsigned NextTempRegID;
 
   std::vector<Record *> RequiredFeatures;
-  std::vector<std::unique_ptr<PredicateMatcher>> EpilogueMatchers;
 
   ArrayRef<SMLoc> SrcLoc;
 
@@ -782,9 +706,16 @@ public:
   action_iterator insertAction(action_iterator InsertPt, Args &&... args);
 
   /// Define an instruction without emitting any code to do so.
-  unsigned implicitlyDefineInsnVar(InstructionMatcher &Matcher);
-
-  unsigned getInsnVarID(InstructionMatcher &InsnMatcher) const;
+  /// 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;
   DefinedInsnVariablesMap::const_iterator defined_insn_vars_begin() const {
     return InsnVariableIDs.begin();
   }
@@ -806,7 +737,7 @@ public:
   mutatable_insns() const {
     return make_range(mutatable_insns_begin(), mutatable_insns_end());
   }
-  void reserveInsnMatcherForMutation(InstructionMatcher *InsnMatcher) {
+  void reserveInsnMatcherForMutation(const InstructionMatcher *InsnMatcher) {
     bool R = MutatableInsns.erase(InsnMatcher);
     assert(R && "Reserving a mutatable insn that isn't available");
     (void)R;
@@ -834,10 +765,11 @@ public:
     return I->second;
   }
 
-  InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
+  const InstructionMatcher &getInstructionMatcher(StringRef SymbolicName) const;
   const OperandMatcher &getOperandMatcher(StringRef Name) const;
 
-  void optimize() override;
+  void emitCaptureOpcodes(MatchTable &Table);
+
   void emit(MatchTable &Table) override;
 
   /// Compare the priority of this object and B.
@@ -849,11 +781,7 @@ public:
   /// matcher.
   unsigned countRendererFns() const;
 
-  std::unique_ptr<PredicateMatcher> popFirstCondition() override;
-  const PredicateMatcher &getFirstCondition() const override;
-  LLTCodeGen getFirstConditionAsRootType();
-  bool hasFirstCondition() const override;
-  unsigned getNumOperands() const;
+  std::unique_ptr<PredicateMatcher> forgetFirstCondition() override;
 
   // FIXME: Remove this as soon as possible
   InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
@@ -861,9 +789,6 @@ 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()); }
 };
@@ -874,69 +799,58 @@ 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 predicate and add it to the matcher.
+  /// Construct a new operand predicate and add it to the matcher.
   template <class Kind, class... Args>
-  Optional<Kind *> addPredicate(Args &&... args);
+  Optional<Kind *> addPredicate(Args&&... args) {
+    Predicates.emplace_back(
+        llvm::make_unique<Kind>(std::forward<Args>(args)...));
+    return static_cast<Kind *>(Predicates.back().get());
+  }
 
-  typename PredicatesTy::iterator predicates_begin() {
+  typename PredicateVec::const_iterator predicates_begin() const {
     return Predicates.begin();
   }
-  typename PredicatesTy::iterator predicates_end() {
+  typename PredicateVec::const_iterator predicates_end() const {
     return Predicates.end();
   }
-  iterator_range<typename PredicatesTy::iterator> predicates() {
+  iterator_range<typename PredicateVec::const_iterator> predicates() const {
     return make_range(predicates_begin(), predicates_end());
   }
-  typename PredicatesTy::size_type predicates_size() const {
+  typename PredicateVec::size_type predicates_size() const {
     return Predicates.size();
   }
   bool predicates_empty() const { return Predicates.empty(); }
 
   std::unique_ptr<PredicateTy> predicates_pop_front() {
     std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
-    Predicates.pop_front();
-    Optimized = true;
+    Predicates.erase(Predicates.begin());
     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) {
-    if (Predicates.empty() && !Optimized) {
+  void emitPredicateListOpcodes(MatchTable &Table, Args &&... args) const {
+    if (Predicates.empty()) {
       Table << MatchTable::Comment(getNoPredicateComment())
             << MatchTable::LineBreak;
       return;
     }
 
-    for (const auto &Predicate : predicates())
+    unsigned OpIdx = (*predicates_begin())->getOpIdx();
+    (void)OpIdx;
+    for (const auto &Predicate : predicates()) {
+      assert(Predicate->getOpIdx() == OpIdx &&
+             "Checks touch different operands?");
       Predicate->emitPredicateOpcodes(Table, std::forward<Args>(args)...);
+    }
   }
 };
 
@@ -954,7 +868,6 @@ public:
   /// are currently not compared between each other.
   enum PredicateKind {
     IPM_Opcode,
-    IPM_NumOperands,
     IPM_ImmPredicate,
     IPM_AtomicOrderingMMO,
     IPM_MemoryLLTSize,
@@ -980,9 +893,7 @@ 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,
@@ -991,23 +902,16 @@ 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.
@@ -1023,10 +927,20 @@ 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 <>
@@ -1045,17 +959,12 @@ public:
       : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
         MatchingName(MatchingName) {}
 
-  static bool classof(const PredicateMatcher *P) {
+  static bool classof(const OperandPredicateMatcher *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.
@@ -1064,16 +973,6 @@ 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);
@@ -1086,31 +985,17 @@ 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")
-          << getValue() << MatchTable::LineBreak;
+          << MatchTable::NamedValue(Ty.getCxxEnumValue())
+          << 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
@@ -1342,18 +1227,7 @@ public:
     assert(SymbolicName.empty() && "Operand already has a symbolic name");
     SymbolicName = Name;
   }
-
-  /// 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 getOperandIndex() const { return OpIdx; }
   unsigned getInsnVarID() const;
 
   std::string getOperandExpr(unsigned InsnVarID) const {
@@ -1366,19 +1240,23 @@ 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) {
-    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;
-    }
+  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;
 
     emitPredicateListOpcodes(Table, Rule);
   }
@@ -1386,7 +1264,7 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  bool isHigherPriorityThan(OperandMatcher &B) {
+  bool isHigherPriorityThan(const OperandMatcher &B) const {
     // Operand matchers involving more predicates have higher priority.
     if (predicates_size() > B.predicates_size())
       return true;
@@ -1394,7 +1272,7 @@ public:
       return false;
 
     // This assumes that predicates are added in a consistent order.
-    for (auto &&Predicate : zip(predicates(), B.predicates())) {
+    for (const 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)))
@@ -1406,7 +1284,7 @@ public:
 
   /// Report the maximum number of temporary operands needed by the operand
   /// matcher.
-  unsigned countRendererFns() {
+  unsigned countRendererFns() const {
     return std::accumulate(
         predicates().begin(), predicates().end(), 0,
         [](unsigned A,
@@ -1419,7 +1297,7 @@ public:
     return AllocatedTemporariesBaseID;
   }
 
-  bool isSameAsAnotherOperand() {
+  bool isSameAsAnotherOperand() const {
     for (const auto &Predicate : predicates())
       if (isa<SameOperandMatcher>(Predicate))
         return true;
@@ -1427,6 +1305,21 @@ 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())
@@ -1470,11 +1363,15 @@ 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<PredicateMatcher>::getNoPredicateComment() const {
+PredicateListMatcher<InstructionPredicateMatcher>::getNoPredicateComment() const {
   return "No instruction predicates";
 }
 
@@ -1483,17 +1380,7 @@ 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) {}
 
@@ -1505,19 +1392,12 @@ 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) << getValue()
+          << MatchTable::IntValue(InsnVarID)
+          << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
           << MatchTable::LineBreak;
   }
 
@@ -1544,17 +1424,8 @@ 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.
 ///
@@ -1632,17 +1503,10 @@ public:
       : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
         Order(Order), Comparator(Comparator) {}
 
-  static bool classof(const PredicateMatcher *P) {
+  static bool classof(const InstructionPredicateMatcher *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";
@@ -1741,7 +1605,8 @@ public:
 /// Typical predicates include:
 /// * Has a specific opcode.
 /// * Has an nsw/nuw flag or doesn't.
-class InstructionMatcher final : public PredicateListMatcher<PredicateMatcher> {
+class InstructionMatcher
+    : public PredicateListMatcher<InstructionPredicateMatcher> {
 protected:
   typedef std::vector<std::unique_ptr<OperandMatcher>> OperandVec;
 
@@ -1762,17 +1627,9 @@ 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 getInsnVarID() const { return InsnVarID; }
+  unsigned getVarID() const { return InsnVarID; }
 
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
@@ -1788,7 +1645,7 @@ public:
   OperandMatcher &getOperand(unsigned OpIdx) {
     auto I = std::find_if(Operands.begin(), Operands.end(),
                           [&OpIdx](const std::unique_ptr<OperandMatcher> &X) {
-                            return X->getOpIdx() == OpIdx;
+                            return X->getOperandIndex() == OpIdx;
                           });
     if (I != Operands.end())
       return **I;
@@ -1811,18 +1668,21 @@ public:
 
   void pop_front() { Operands.erase(Operands.begin()); }
 
-  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) {
+  /// Emit MatchTable opcodes to check the shape of the match and capture
+  /// instructions into the MIs table.
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) {
     Table << MatchTable::Opcode("GIM_CheckNumOperands")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Expected")
           << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
+    for (const auto &Operand : Operands)
+      Operand->emitCaptureOpcodes(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);
   }
@@ -1830,19 +1690,17 @@ public:
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
-  bool isHigherPriorityThan(InstructionMatcher &B) {
+  bool isHigherPriorityThan(const InstructionMatcher &B) const {
     // 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 (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))
+    for (const auto &Predicate : zip(predicates(), B.predicates())) {
+      if (std::get<0>(Predicate)->isHigherPriorityThan(*std::get<1>(Predicate)))
         return true;
-      if (R->isHigherPriorityThan(*L))
+      if (std::get<1>(Predicate)->isHigherPriorityThan(*std::get<0>(Predicate)))
         return false;
     }
 
@@ -1858,13 +1716,13 @@ public:
 
   /// Report the maximum number of temporary operands needed by the instruction
   /// matcher.
-  unsigned countRendererFns() {
-    return std::accumulate(
-               predicates().begin(), predicates().end(), 0,
-               [](unsigned A,
-                  const std::unique_ptr<PredicateMatcher> &Predicate) {
-                 return A + Predicate->countRendererFns();
-               }) +
+  unsigned countRendererFns() const {
+    return std::accumulate(predicates().begin(), predicates().end(), 0,
+                           [](unsigned A,
+                              const std::unique_ptr<InstructionPredicateMatcher>
+                                  &Predicate) {
+                             return A + Predicate->countRendererFns();
+                           }) +
            std::accumulate(
                Operands.begin(), Operands.end(), 0,
                [](unsigned A, const std::unique_ptr<OperandMatcher> &Operand) {
@@ -1872,30 +1730,24 @@ public:
                });
   }
 
-  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();
+  bool isConstantInstruction() const {
+    for (const auto &P : predicates())
+      if (const InstructionOpcodeMatcher *Opcode =
+              dyn_cast<InstructionOpcodeMatcher>(P.get()))
+        return Opcode->isConstantInstruction();
+    return false;
   }
 };
 
-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 {};
+template <>
+template <class Kind, class... Args>
+Optional<Kind *>
+PredicateListMatcher<InstructionPredicateMatcher>::addPredicate(
+    Args &&... args) {
+  InstructionMatcher *InstMatcher = static_cast<InstructionMatcher *>(this);
+  Predicates.emplace_back(llvm::make_unique<Kind>(InstMatcher->getVarID(),
+                                                  std::forward<Args>(args)...));
+  return static_cast<Kind *>(Predicates.back().get());
 }
 
 /// Generates code to check that the operand is a register defined by an
@@ -1923,20 +1775,17 @@ public:
 
   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 
-  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 emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    unsigned InsnID =
+        Rule.defineInsnVar(Table, *InsnMatcher, InsnVarID, getOpIdx());
+    (void)InsnID;
+    assert(InsnMatcher->getVarID() == InsnID &&
+           "Mismatch between build and emit");
+    InsnMatcher->emitCaptureOpcodes(Table, Rule);
   }
 
   void emitPredicateOpcodes(MatchTable &Table,
                             RuleMatcher &Rule) const override {
-    emitCaptureOpcodes(Table, Rule);
     InsnMatcher->emitPredicateOpcodes(Table, Rule);
   }
 
@@ -2010,7 +1859,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.getOpIdx())
+          << MatchTable::IntValue(Operand.getOperandIndex())
           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
   }
 };
@@ -2046,7 +1895,7 @@ public:
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
           << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
-          << MatchTable::IntValue(Operand.getOpIdx())
+          << MatchTable::IntValue(Operand.getOperandIndex())
           << MatchTable::NamedValue(
                  (ZeroRegisterDef->getValue("Namespace")
                       ? ZeroRegisterDef->getValueAsString("Namespace")
@@ -2077,7 +1926,7 @@ public:
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode(Signed ? "GIR_CopyConstantAsSImm"
                                        : "GIR_CopyConstantAsUImm")
@@ -2108,7 +1957,7 @@ public:
   const StringRef getSymbolicName() const { return SymbolicName; }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    const InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode("GIR_CopyFConstantAsFPImm")
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
@@ -2148,7 +1997,7 @@ public:
           << MatchTable::Comment("NewInsnID") << MatchTable::IntValue(NewInsnID)
           << MatchTable::Comment("OldInsnID")
           << MatchTable::IntValue(OldInsnVarID) << MatchTable::Comment("OpIdx")
-          << MatchTable::IntValue(Operand.getOpIdx())
+          << MatchTable::IntValue(Operand.getOperandIndex())
           << MatchTable::Comment("SubRegIdx")
           << MatchTable::IntValue(SubReg->EnumValue)
           << MatchTable::Comment(SymbolicName) << MatchTable::LineBreak;
@@ -2297,7 +2146,8 @@ public:
   }
 
   void emitRenderOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
-    InstructionMatcher &InsnMatcher = Rule.getInstructionMatcher(SymbolicName);
+    const InstructionMatcher &InsnMatcher =
+        Rule.getInstructionMatcher(SymbolicName);
     unsigned OldInsnVarID = Rule.getInsnVarID(InsnMatcher);
     Table << MatchTable::Opcode("GIR_CustomRenderer")
           << MatchTable::Comment("InsnID") << MatchTable::IntValue(InsnID)
@@ -2343,7 +2193,7 @@ class BuildMIAction : public MatchAction {
 private:
   unsigned InsnID;
   const CodeGenInstruction *I;
-  InstructionMatcher *Matched;
+  const InstructionMatcher *Matched;
   std::vector<std::unique_ptr<OperandRenderer>> OperandRenderers;
 
   /// True if the instruction can be built solely by mutating the opcode.
@@ -2358,7 +2208,7 @@ private:
       if (const auto *Copy = dyn_cast<CopyRenderer>(&*Renderer.value())) {
         const OperandMatcher &OM = Rule.getOperandMatcher(Copy->getSymbolicName());
         if (Insn != &OM.getInstructionMatcher() ||
-            OM.getOpIdx() != Renderer.index())
+            OM.getOperandIndex() != Renderer.index())
           return false;
       } else
         return false;
@@ -2375,7 +2225,7 @@ public:
   const CodeGenInstruction *getCGI() const { return I; }
 
   void chooseInsnToMutate(RuleMatcher &Rule) {
-    for (auto *MutateCandidate : Rule.mutatable_insns()) {
+    for (const auto *MutateCandidate : Rule.mutatable_insns()) {
       if (canMutate(Rule, MutateCandidate)) {
         // Take the first one we're offered that we're able to mutate.
         Rule.reserveInsnMatcherForMutation(MutateCandidate);
@@ -2567,13 +2417,27 @@ action_iterator RuleMatcher::insertAction(action_iterator InsertPt,
                          llvm::make_unique<Kind>(std::forward<Args>(args)...));
 }
 
-unsigned RuleMatcher::implicitlyDefineInsnVar(InstructionMatcher &Matcher) {
+unsigned
+RuleMatcher::implicitlyDefineInsnVar(const InstructionMatcher &Matcher) {
   unsigned NewInsnVarID = NextInsnVarID++;
   InsnVariableIDs[&Matcher] = NewInsnVarID;
   return NewInsnVarID;
 }
 
-unsigned RuleMatcher::getInsnVarID(InstructionMatcher &InsnMatcher) const {
+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 {
   const auto &I = InsnVariableIDs.find(&InsnMatcher);
   if (I != InsnVariableIDs.end())
     return I->second;
@@ -2591,7 +2455,7 @@ void RuleMatcher::defineOperand(StringRef SymbolicName, OperandMatcher &OM) {
   OM.addPredicate<SameOperandMatcher>(OM.getSymbolicName());
 }
 
-InstructionMatcher &
+const InstructionMatcher &
 RuleMatcher::getInstructionMatcher(StringRef SymbolicName) const {
   for (const auto &I : InsnVariableIDs)
     if (I.first->getSymbolicName() == SymbolicName)
@@ -2610,10 +2474,25 @@ 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
@@ -2627,9 +2506,7 @@ 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(("Rule ID " + Twine(RuleID) + " //").str())
+        << MatchTable::Comment("On fail goto") << MatchTable::JumpTarget(LabelID)
         << MatchTable::LineBreak;
 
   if (!RequiredFeatures.empty()) {
@@ -2638,6 +2515,8 @@ 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.
@@ -2697,18 +2576,12 @@ 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);
@@ -2776,7 +2649,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().getInsnVarID());
+  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getVarID());
 
   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
@@ -2784,7 +2657,7 @@ void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
         << MatchTable::Comment("OtherMI")
         << MatchTable::IntValue(OtherInsnVarID)
         << MatchTable::Comment("OtherOpIdx")
-        << MatchTable::IntValue(OtherOM.getOpIdx())
+        << MatchTable::IntValue(OtherOM.getOperandIndex())
         << MatchTable::LineBreak;
 }
 
@@ -2827,8 +2700,6 @@ private:
   // Rule coverage information.
   Optional<CodeGenCoverage> RuleCoverage;
 
-  void gatherOpcodeValues();
-  void gatherTypeIDValues();
   void gatherNodeEquivs();
   Record *findNodeEquiv(Record *N) const;
   const CodeGenInstruction *getEquivNode(Record &Equiv,
@@ -2879,15 +2750,16 @@ 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 MatcherStorage is used as a memory container
+  /// they share. \p StorageGroupMatcher 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 if GroupT = GroupMatcher:
+  /// What this optimization does looks like:
   /// Output without optimization:
   /// \verbatim
   /// # R1
@@ -2908,19 +2780,13 @@ public:
   ///  # R2
   ///   # predicate C
   /// \endverbatim
-  template <class GroupT>
-  static std::vector<Matcher *> optimizeRules(
+  std::vector<Matcher *> optimizeRules(
       ArrayRef<Matcher *> Rules,
-      std::vector<std::unique_ptr<Matcher>> &MatcherStorage);
-};
+      std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
 
-void GlobalISelEmitter::gatherOpcodeValues() {
-  InstructionOpcodeMatcher::initOpcodeValuesMap(Target);
-}
-
-void GlobalISelEmitter::gatherTypeIDValues() {
-  LLTOperandMatcher::initTypeIDValuesMap();
-}
+  MatchTable buildMatchTable(MutableArrayRef<RuleMatcher> Rules, bool Optimize,
+                             bool WithCoverage);
+};
 
 void GlobalISelEmitter::gatherNodeEquivs() {
   assert(NodeEquivs.empty());
@@ -3656,6 +3522,7 @@ 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);
@@ -3911,53 +3778,35 @@ void GlobalISelEmitter::emitImmPredicates(
      << "}\n";
 }
 
-template <class GroupT>
 std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
     ArrayRef<Matcher *> Rules,
-    std::vector<std::unique_ptr<Matcher>> &MatcherStorage) {
-
+    std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) {
   std::vector<Matcher *> OptRules;
-  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();
+  // 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;
       OptRules.push_back(CurrentGroup.get());
-      MatcherStorage.emplace_back(std::move(CurrentGroup));
-      ++NumGroups;
+      StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+      CurrentGroup = make_unique<GroupMatcher>();
+      assert(CurrentGroup->conditions_empty());
     }
-    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);
+    if (CurrentGroup->conditions_empty())
+      CurrentGroup->addCondition(std::move(Predicate));
+    CurrentGroup->addRule(*Rule);
   }
-  ProcessCurrentGroup();
-
-  DEBUG(dbgs() << "NumGroups: " << NumGroups << "\n");
-  assert(CurrentGroup->empty() && "The last group wasn't properly processed");
+  if (!CurrentGroup->conditions_empty()) {
+    ++NbGroup;
+    OptRules.push_back(CurrentGroup.get());
+    StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+  }
+  LLVM_DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
   return OptRules;
 }
 
@@ -3971,15 +3820,9 @@ GlobalISelEmitter::buildMatchTable(MutableArrayRef<RuleMatcher> Rules,
   if (!Optimize)
     return MatchTable::buildTable(InputRules, WithCoverage);
 
-  for (Matcher *Rule : InputRules)
-    Rule->optimize();
-
-  std::vector<std::unique_ptr<Matcher>> MatcherStorage;
+  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
   std::vector<Matcher *> OptRules =
-      optimizeRules<GroupMatcher>(InputRules, MatcherStorage);
-
-  for (Matcher *Rule : OptRules)
-    Rule->optimize();
+      optimizeRules(InputRules, StorageGroupMatcher);
 
   return MatchTable::buildTable(OptRules, WithCoverage);
 }
@@ -3999,11 +3842,6 @@ 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();
 
@@ -4092,8 +3930,8 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
 
   OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n"
      << ", State(" << MaxTemporaries << "),\n"
-     << "ISelInfo(TypeObjects, NumTypeObjects, FeatureBitsets"
-     << ", ComplexPredicateFns, CustomRenderers)\n"
+     << "ISelInfo({TypeObjects, FeatureBitsets, ComplexPredicateFns, "
+        "CustomRenderers})\n"
      << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n\n";
 
   OS << "#ifdef GET_GLOBALISEL_IMPL\n";
@@ -4135,8 +3973,7 @@ void GlobalISelEmitter::run(raw_ostream &OS) {
     TypeObject.emitCxxEnumValue(OS);
     OS << ",\n";
   }
-  OS << "};\n";
-  OS << "const static size_t NumTypeObjects = " << TypeObjects.size() << ";\n"
+  OS << "};\n"
      << "const static LLT TypeObjects[] = {\n";
   for (const auto &TypeObject : TypeObjects) {
     OS << "  ";
@@ -4315,154 +4152,62 @@ void GlobalISelEmitter::declareSubtargetFeature(Record *Predicate) {
         Predicate, SubtargetFeatureInfo(Predicate, SubtargetFeatures.size()));
 }
 
-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 {
+std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() {
   assert(!insnmatchers_empty() &&
-         "Trying to get a condition from an empty RuleMatcher");
+         "Trying to forget something that does not exist");
 
   InstructionMatcher &Matcher = insnmatchers_front();
+  std::unique_ptr<PredicateMatcher> Condition;
   if (!Matcher.predicates_empty())
-    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");
+    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;
 }
 
-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(
+bool GroupMatcher::lastConditionMatches(
     const PredicateMatcher &Predicate) const {
-
-  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();
+  const auto &LastCondition = conditions_back();
+  return Predicate.isIdentical(*LastCondition);
 }
 
 void GroupMatcher::emit(MatchTable &Table) {
-  unsigned LabelID = ~0U;
-  if (!Conditions.empty()) {
-    LabelID = Table.allocateLabelID();
+  unsigned LabelID = Table.allocateLabelID();
+  if (!conditions_empty()) {
     Table << MatchTable::Opcode("GIM_Try", +1)
           << MatchTable::Comment("On fail goto")
           << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
+    for (auto &Condition : Conditions)
+      Condition->emitPredicateOpcodes(
+          Table, *static_cast<RuleMatcher *>(*Rules.begin()));
   }
-  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
+  // Emit the conditions.
+  // Then checks apply the rules.
+  for (const auto &Rule : Rules)
+    Rule->emit(Table);
+  // If we don't succeeded for that block, that means we are not going to select
+  // this instruction.
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+    Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
           << MatchTable::Label(LabelID);
+  }
 }
 
-unsigned OperandMatcher::getInsnVarID() const { return Insn.getInsnVarID(); }
+unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); }
 
 } // end anonymous namespace