Index: utils/TableGen/GlobalISelEmitter.cpp
===================================================================
--- utils/TableGen/GlobalISelEmitter.cpp
+++ utils/TableGen/GlobalISelEmitter.cpp
@@ -168,6 +168,8 @@
 
     return Ty.getSizeInBits() < Other.Ty.getSizeInBits();
   }
+
+  bool operator==(const LLTCodeGen &B) const { return Ty == B.Ty; }
 };
 
 class InstructionMatcher;
@@ -561,9 +563,38 @@
 
 class OperandMatcher;
 class MatchAction;
+class PredicateMatcher;
+class RuleMatcher;
+
+class Matcher {
+public:
+  virtual ~Matcher() = default;
+  virtual void emit(MatchTable &Table) = 0;
+};
+
+class GroupMatcher : public Matcher {
+  SmallVector<std::unique_ptr<PredicateMatcher>, 8> Conditions;
+  SmallVector<Matcher *, 8> Rules;
+
+public:
+  void addCondition(std::unique_ptr<PredicateMatcher> &&Predicate) {
+    Conditions.emplace_back(std::move(Predicate));
+  }
+  void addRule(Matcher &Rule) { Rules.push_back(&Rule); }
+  const std::unique_ptr<PredicateMatcher> &conditions_back() const {
+    return Conditions.back();
+  }
+  bool lastConditionMatches(const PredicateMatcher &Predicate) const;
+  bool conditions_empty() const { return Conditions.empty(); }
+  void clear() {
+    Conditions.clear();
+    Rules.clear();
+  }
+  void emit(MatchTable &Table) override;
+};
 
 /// Generates code to check that a match rule matches.
-class RuleMatcher {
+class RuleMatcher : public Matcher {
 public:
   using ActionVec = std::vector<std::unique_ptr<MatchAction>>;
   using action_iterator = ActionVec::iterator;
@@ -641,6 +672,10 @@
   /// 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);
@@ -699,7 +734,7 @@
 
   void emitCaptureOpcodes(MatchTable &Table);
 
-  void emit(MatchTable &Table);
+  void emit(MatchTable &Table) override;
 
   /// Compare the priority of this object and B.
   ///
@@ -710,11 +745,16 @@
   /// matcher.
   unsigned countRendererFns() const;
 
+  std::unique_ptr<PredicateMatcher> forgetFirstCondition();
+
   // FIXME: Remove this as soon as possible
-  InstructionMatcher &insnmatcher_front() const { return *Matchers.front(); }
+  InstructionMatcher &insnmatchers_front() const { return *Matchers.front(); }
 
   unsigned allocateOutputInsnID() { return NextOutputInsnID++; }
   unsigned allocateTempRegID() { return NextTempRegID++; }
+
+  bool insnmatchers_empty() const { return Matchers.empty(); }
+  void insnmatchers_pop_front() { Matchers.erase(Matchers.begin()); }
 };
 
 uint64_t RuleMatcher::NextRuleID = 0;
@@ -751,6 +791,13 @@
   typename PredicateVec::size_type predicates_size() const {
     return Predicates.size();
   }
+  bool predicates_empty() const { return Predicates.empty(); }
+
+  std::unique_ptr<PredicateTy> predicates_pop_front() {
+    std::unique_ptr<PredicateTy> Front = std::move(Predicates.front());
+    Predicates.erase(Predicates.begin());
+    return Front;
+  }
 
   /// Emit MatchTable opcodes that tests whether all the predicates are met.
   template <class... Args>
@@ -761,18 +808,17 @@
       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)...);
+    }
   }
 };
 
-/// Generates code to check a predicate of an operand.
-///
-/// Typical predicates include:
-/// * Operand is a particular register.
-/// * Operand is assigned a particular register bank.
-/// * Operand is an MBB.
-class OperandPredicateMatcher {
+class PredicateMatcher {
 public:
   /// This enum is used for RTTI and also defines the priority that is given to
   /// the predicate when generating the matcher code. Kinds with higher priority
@@ -781,7 +827,13 @@
   /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter
   /// but OPM_Int must have priority over OPM_RegBank since constant integers
   /// are represented by a virtual register defined by a G_CONSTANT instruction.
+  ///
+  /// Note: The relative priority between IPM_ and OPM_ does not matter, they
+  /// are currently not compared between each other.
   enum PredicateKind {
+    IPM_Opcode,
+    IPM_ImmPredicate,
+    IPM_AtomicOrderingMMO,
     OPM_SameOperand,
     OPM_ComplexPattern,
     OPM_IntrinsicID,
@@ -796,24 +848,52 @@
 
 protected:
   PredicateKind Kind;
+  unsigned InsnVarID;
+  unsigned OpIdx;
 
 public:
-  OperandPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
-  virtual ~OperandPredicateMatcher() {}
+  PredicateMatcher(PredicateKind Kind, unsigned InsnVarID, unsigned OpIdx = ~0)
+      : Kind(Kind), InsnVarID(InsnVarID), OpIdx(OpIdx) {}
+
+  unsigned getOpIdx() const { return OpIdx; }
+  virtual ~PredicateMatcher() = default;
+  /// Emit MatchTable opcodes that check the predicate for the given operand.
+  virtual void emitPredicateOpcodes(MatchTable &Table,
+                                    RuleMatcher &Rule) const = 0;
 
   PredicateKind getKind() const { return Kind; }
 
+  virtual bool isIdentical(const PredicateMatcher &B) const {
+    if (InsnVarID != 0 || OpIdx != (unsigned)~0) {
+      // We currently don't hoist the record of instruction properly.
+      // Therefore we can only work on the orig instruction (InsnVarID
+      // == 0).
+      DEBUG(dbgs() << "Non-zero instr ID not supported yet\n");
+      return false;
+    }
+    return B.getKind() == getKind() && InsnVarID == B.InsnVarID &&
+           OpIdx == B.OpIdx;
+  }
+};
+
+/// Generates code to check a predicate of an operand.
+///
+/// Typical predicates include:
+/// * Operand is a particular register.
+/// * Operand is assigned a particular register bank.
+/// * Operand is an MBB.
+class OperandPredicateMatcher : public PredicateMatcher {
+public:
+  OperandPredicateMatcher(PredicateKind Kind, unsigned InsnVarID,
+                          unsigned OpIdx)
+      : PredicateMatcher(Kind, InsnVarID, OpIdx) {}
+  virtual ~OperandPredicateMatcher() {}
+
   /// Emit MatchTable opcodes to capture instructions into the MIs table.
   ///
   /// Only InstructionOperandMatcher needs to do anything for this method the
   /// rest just walk the tree.
-  virtual void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                                  unsigned InsnVarID, unsigned OpIdx) const {}
-
-  /// Emit MatchTable opcodes that check the predicate for the given operand.
-  virtual void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                                    unsigned InsnVarID,
-                                    unsigned OpIdx) const = 0;
+  virtual void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {}
 
   /// Compare the priority of this object and B.
   ///
@@ -837,15 +917,16 @@
   std::string MatchingName;
 
 public:
-  SameOperandMatcher(StringRef MatchingName)
-      : OperandPredicateMatcher(OPM_SameOperand), MatchingName(MatchingName) {}
+  SameOperandMatcher(StringRef MatchingName, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_SameOperand, InsnVarID, OpIdx),
+        MatchingName(MatchingName) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_SameOperand;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override;
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override;
 };
 
 /// Generates code to check that an operand is a particular LLT.
@@ -856,17 +937,21 @@
 public:
   static std::set<LLTCodeGen> KnownTypes;
 
-  LLTOperandMatcher(const LLTCodeGen &Ty)
-      : OperandPredicateMatcher(OPM_LLT), Ty(Ty) {
+  LLTOperandMatcher(const LLTCodeGen &Ty, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_LLT, InsnVarID, OpIdx), Ty(Ty) {
     KnownTypes.insert(Ty);
   }
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_LLT;
   }
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Ty == cast<LLTOperandMatcher>(&B)->Ty;
+  }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  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")
@@ -892,18 +977,21 @@
   unsigned SizeInBits;
 
 public:
-  PointerToAnyOperandMatcher(unsigned SizeInBits)
-      : OperandPredicateMatcher(OPM_PointerToAny), SizeInBits(SizeInBits) {}
+  PointerToAnyOperandMatcher(unsigned SizeInBits, unsigned InsnVarID,
+                             unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_PointerToAny, InsnVarID, OpIdx),
+        SizeInBits(SizeInBits) {}
 
   static bool classof(const OperandPredicateMatcher *P) {
     return P->getKind() == OPM_PointerToAny;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
-    Table << MatchTable::Opcode("GIM_CheckPointerToAny") << MatchTable::Comment("MI")
-          << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
-          << MatchTable::IntValue(OpIdx) << MatchTable::Comment("SizeInBits")
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    Table << MatchTable::Opcode("GIM_CheckPointerToAny")
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
+          << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
+          << MatchTable::Comment("SizeInBits")
           << MatchTable::IntValue(SizeInBits) << MatchTable::LineBreak;
   }
 };
@@ -917,17 +1005,20 @@
   unsigned getAllocatedTemporariesBaseID() const;
 
 public:
+  bool isIdentical(const PredicateMatcher &B) const override { return false; }
+
   ComplexPatternOperandMatcher(const OperandMatcher &Operand,
-                               const Record &TheDef)
-      : OperandPredicateMatcher(OPM_ComplexPattern), Operand(Operand),
-        TheDef(TheDef) {}
+                               const Record &TheDef, unsigned InsnVarID,
+                               unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_ComplexPattern, InsnVarID, OpIdx),
+        Operand(Operand), TheDef(TheDef) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_ComplexPattern;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     unsigned ID = getAllocatedTemporariesBaseID();
     Table << MatchTable::Opcode("GIM_CheckComplexPattern")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
@@ -948,15 +1039,21 @@
   const CodeGenRegisterClass &RC;
 
 public:
-  RegisterBankOperandMatcher(const CodeGenRegisterClass &RC)
-      : OperandPredicateMatcher(OPM_RegBank), RC(RC) {}
+  RegisterBankOperandMatcher(const CodeGenRegisterClass &RC, unsigned InsnVarID,
+                             unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_RegBank, InsnVarID, OpIdx), RC(RC) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           RC.getDef() == cast<RegisterBankOperandMatcher>(&B)->RC.getDef();
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_RegBank;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckRegBankForClass")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
@@ -969,14 +1066,15 @@
 /// Generates code to check that an operand is a basic block.
 class MBBOperandMatcher : public OperandPredicateMatcher {
 public:
-  MBBOperandMatcher() : OperandPredicateMatcher(OPM_MBB) {}
+  MBBOperandMatcher(unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_MBB, InsnVarID, OpIdx) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_MBB;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckIsMBB") << MatchTable::Comment("MI")
           << MatchTable::IntValue(InsnVarID) << MatchTable::Comment("Op")
           << MatchTable::IntValue(OpIdx) << MatchTable::LineBreak;
@@ -990,15 +1088,20 @@
   int64_t Value;
 
 public:
-  ConstantIntOperandMatcher(int64_t Value)
-      : OperandPredicateMatcher(OPM_Int), Value(Value) {}
+  ConstantIntOperandMatcher(int64_t Value, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_Int, InsnVarID, OpIdx), Value(Value) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Value == cast<ConstantIntOperandMatcher>(&B)->Value;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_Int;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckConstantInt")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
@@ -1013,15 +1116,21 @@
   int64_t Value;
 
 public:
-  LiteralIntOperandMatcher(int64_t Value)
-      : OperandPredicateMatcher(OPM_LiteralInt), Value(Value) {}
+  LiteralIntOperandMatcher(int64_t Value, unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_LiteralInt, InsnVarID, OpIdx),
+        Value(Value) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           Value == cast<LiteralIntOperandMatcher>(&B)->Value;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_LiteralInt;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckLiteralInt")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
@@ -1035,15 +1144,21 @@
   const CodeGenIntrinsic *II;
 
 public:
-  IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II)
-      : OperandPredicateMatcher(OPM_IntrinsicID), II(II) {}
+  IntrinsicIDOperandMatcher(const CodeGenIntrinsic *II, unsigned InsnVarID,
+                            unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_IntrinsicID, InsnVarID, OpIdx), II(II) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return OperandPredicateMatcher::isIdentical(B) &&
+           II == cast<IntrinsicIDOperandMatcher>(&B)->II;
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_IntrinsicID;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID, unsigned OpIdx) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckIntrinsicID")
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Op") << MatchTable::IntValue(OpIdx)
@@ -1079,6 +1194,7 @@
     SymbolicName = Name;
   }
   unsigned getOperandIndex() const { return OpIdx; }
+  unsigned getInsnVarID() const;
 
   std::string getOperandExpr(unsigned InsnVarID) const {
     return "State.MIs[" + llvm::to_string(InsnVarID) + "]->getOperand(" +
@@ -1091,26 +1207,24 @@
                               bool OperandIsAPointer);
 
   /// Emit MatchTable opcodes to capture instructions into the MIs table.
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                          unsigned InsnVarID) const {
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
     for (const auto &Predicate : predicates())
-      Predicate->emitCaptureOpcodes(Table, Rule, InsnVarID, OpIdx);
+      Predicate->emitCaptureOpcodes(Table, Rule);
   }
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarID matches all the predicates and all the operands.
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID) const {
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
     std::string Comment;
     raw_string_ostream CommentOS(Comment);
-    CommentOS << "MIs[" << InsnVarID << "] ";
+    CommentOS << "MIs[" << getInsnVarID() << "] ";
     if (SymbolicName.empty())
       CommentOS << "Operand " << OpIdx;
     else
       CommentOS << SymbolicName;
     Table << MatchTable::Comment(CommentOS.str()) << MatchTable::LineBreak;
 
-    emitPredicateListOpcodes(Table, Rule, InsnVarID, OpIdx);
+    emitPredicateListOpcodes(Table, Rule);
   }
 
   /// Compare the priority of this object and B.
@@ -1163,14 +1277,17 @@
 template <class Kind, class... Args>
 Optional<Kind *>
 PredicateListMatcher<OperandPredicateMatcher>::addPredicate(Args &&... args) {
+  auto *OpMatcher = static_cast<OperandMatcher *>(this);
   if (static_cast<OperandMatcher *>(this)->isSameAsAnotherOperand())
     return None;
-  Predicates.emplace_back(llvm::make_unique<Kind>(std::forward<Args>(args)...));
+  Predicates.emplace_back(llvm::make_unique<Kind>(
+      std::forward<Args>(args)..., OpMatcher->getInsnVarID(),
+      OpMatcher->getOperandIndex()));
   return static_cast<Kind *>(Predicates.back().get());
 }
 
 Error OperandMatcher::addTypeCheckPredicate(const TypeSetByHwMode &VTy,
-                                                     bool OperandIsAPointer) {
+                                            bool OperandIsAPointer) {
   if (!VTy.isMachineValueType())
     return failedImport("unsupported typeset");
 
@@ -1199,30 +1316,12 @@
 /// Typical predicates include:
 /// * The opcode of the instruction is a particular value.
 /// * The nsw/nuw flag is/isn't set.
-class InstructionPredicateMatcher {
-protected:
-  /// This enum is used for RTTI and also defines the priority that is given to
-  /// the predicate when generating the matcher code. Kinds with higher priority
-  /// must be tested first.
-  enum PredicateKind {
-    IPM_Opcode,
-    IPM_ImmPredicate,
-    IPM_AtomicOrderingMMO,
-  };
-
-  PredicateKind Kind;
-
+class InstructionPredicateMatcher : public PredicateMatcher {
 public:
-  InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {}
+  InstructionPredicateMatcher(PredicateKind Kind, unsigned InsnVarID)
+      : PredicateMatcher(Kind, InsnVarID) {}
   virtual ~InstructionPredicateMatcher() {}
 
-  PredicateKind getKind() const { return Kind; }
-
-  /// Emit MatchTable opcodes that test whether the instruction named in
-  /// InsnVarID matches the predicate.
-  virtual void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                                    unsigned InsnVarID) const = 0;
-
   /// Compare the priority of this object and B.
   ///
   /// Returns true if this object is more important than B.
@@ -1248,15 +1347,20 @@
   const CodeGenInstruction *I;
 
 public:
-  InstructionOpcodeMatcher(const CodeGenInstruction *I)
-      : InstructionPredicateMatcher(IPM_Opcode), I(I) {}
+  InstructionOpcodeMatcher(unsigned InsnVarID, const CodeGenInstruction *I)
+      : InstructionPredicateMatcher(IPM_Opcode, InsnVarID), I(I) {}
 
-  static bool classof(const InstructionPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == IPM_Opcode;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID) const override {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return InstructionPredicateMatcher::isIdentical(B) &&
+           I == cast<InstructionOpcodeMatcher>(&B)->I;
+  }
+
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode("GIM_CheckOpcode") << MatchTable::Comment("MI")
           << MatchTable::IntValue(InsnVarID)
           << MatchTable::NamedValue(I->Namespace, I->TheDef->getName())
@@ -1319,15 +1423,24 @@
   TreePredicateFn Predicate;
 
 public:
-  InstructionImmPredicateMatcher(const TreePredicateFn &Predicate)
-      : InstructionPredicateMatcher(IPM_ImmPredicate), Predicate(Predicate) {}
+  InstructionImmPredicateMatcher(unsigned InsnVarID,
+                                 const TreePredicateFn &Predicate)
+      : InstructionPredicateMatcher(IPM_ImmPredicate, InsnVarID),
+        Predicate(Predicate) {}
 
-  static bool classof(const InstructionPredicateMatcher *P) {
+  bool isIdentical(const PredicateMatcher &B) const override {
+    return InstructionPredicateMatcher::isIdentical(B) &&
+           Predicate.getOrigPatFragRecord() ==
+               cast<InstructionImmPredicateMatcher>(&B)
+                   ->Predicate.getOrigPatFragRecord();
+  }
+
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == IPM_ImmPredicate;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     Table << MatchTable::Opcode(getMatchOpcodeForPredicate(Predicate))
           << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Predicate")
@@ -1351,17 +1464,17 @@
   AOComparator Comparator;
 
 public:
-  AtomicOrderingMMOPredicateMatcher(StringRef Order,
+  AtomicOrderingMMOPredicateMatcher(unsigned InsnVarID, StringRef Order,
                                     AOComparator Comparator = AO_Exactly)
-      : InstructionPredicateMatcher(IPM_AtomicOrderingMMO), Order(Order),
-        Comparator(Comparator) {}
+      : InstructionPredicateMatcher(IPM_AtomicOrderingMMO, InsnVarID),
+        Order(Order), Comparator(Comparator) {}
 
   static bool classof(const InstructionPredicateMatcher *P) {
     return P->getKind() == IPM_AtomicOrderingMMO;
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID) const override {
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
     StringRef Opcode = "GIM_CheckAtomicOrdering";
 
     if (Comparator == AO_OrStronger)
@@ -1394,13 +1507,18 @@
   OperandVec Operands;
 
   std::string SymbolicName;
+  unsigned InsnVarID;
 
 public:
   InstructionMatcher(RuleMatcher &Rule, StringRef SymbolicName)
-      : Rule(Rule), SymbolicName(SymbolicName) {}
+      : Rule(Rule), SymbolicName(SymbolicName) {
+    InsnVarID = Rule.implicitlyDefineInsnVar(*this);
+  }
 
   RuleMatcher &getRuleMatcher() const { return Rule; }
 
+  unsigned getVarID() const { return InsnVarID; }
+
   /// Add an operand to the matcher.
   OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName,
                              unsigned AllocatedTemporariesBaseID) {
@@ -1434,26 +1552,27 @@
   iterator_range<OperandVec::const_iterator> operands() const {
     return make_range(operands_begin(), operands_end());
   }
+  bool operands_empty() const { return Operands.empty(); }
+
+  void pop_front() { Operands.erase(Operands.begin()); }
 
   /// Emit MatchTable opcodes to check the shape of the match and capture
   /// instructions into the MIs table.
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                          unsigned InsnID) {
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) {
     Table << MatchTable::Opcode("GIM_CheckNumOperands")
-          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnID)
+          << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
           << MatchTable::Comment("Expected")
           << MatchTable::IntValue(getNumOperands()) << MatchTable::LineBreak;
     for (const auto &Operand : Operands)
-      Operand->emitCaptureOpcodes(Table, Rule, InsnID);
+      Operand->emitCaptureOpcodes(Table, Rule);
   }
 
   /// Emit MatchTable opcodes that test whether the instruction named in
   /// InsnVarName matches all the predicates and all the operands.
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID) const {
-    emitPredicateListOpcodes(Table, Rule, InsnVarID);
+  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule) const {
+    emitPredicateListOpcodes(Table, Rule);
     for (const auto &Operand : Operands)
-      Operand->emitPredicateOpcodes(Table, Rule, InsnVarID);
+      Operand->emitPredicateOpcodes(Table, Rule);
   }
 
   /// Compare the priority of this object and B.
@@ -1508,6 +1627,17 @@
   }
 };
 
+template <>
+template <class Kind, class... Args>
+Optional<Kind *>
+PredicateListMatcher<InstructionPredicateMatcher>::addPredicate(
+    Args &&... args) {
+  InstructionMatcher *InstMatcher = static_cast<InstructionMatcher *>(this);
+  Predicates.emplace_back(llvm::make_unique<Kind>(InstMatcher->getVarID(),
+                                                  std::forward<Args>(args)...));
+  return static_cast<Kind *>(Predicates.back().get());
+}
+
 /// Generates code to check that the operand is a register defined by an
 /// instruction that matches the given instruction matcher.
 ///
@@ -1522,27 +1652,29 @@
   std::unique_ptr<InstructionMatcher> InsnMatcher;
 
 public:
-  InstructionOperandMatcher(RuleMatcher &Rule, StringRef SymbolicName)
-      : OperandPredicateMatcher(OPM_Instruction),
+  InstructionOperandMatcher(RuleMatcher &Rule, StringRef SymbolicName,
+                            unsigned InsnVarID, unsigned OpIdx)
+      : OperandPredicateMatcher(OPM_Instruction, InsnVarID, OpIdx),
         InsnMatcher(new InstructionMatcher(Rule, SymbolicName)) {}
 
-  static bool classof(const OperandPredicateMatcher *P) {
+  static bool classof(const PredicateMatcher *P) {
     return P->getKind() == OPM_Instruction;
   }
 
   InstructionMatcher &getInsnMatcher() const { return *InsnMatcher; }
 
-  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                          unsigned InsnID, unsigned OpIdx) const override {
-    unsigned InsnVarID = Rule.defineInsnVar(Table, *InsnMatcher, InsnID, OpIdx);
-    InsnMatcher->emitCaptureOpcodes(Table, Rule, InsnVarID);
+  void emitCaptureOpcodes(MatchTable &Table, RuleMatcher &Rule) const override {
+    unsigned InsnID =
+        Rule.defineInsnVar(Table, *InsnMatcher, InsnVarID, getOpIdx());
+    (void)InsnID;
+    assert(InsnMatcher->getVarID() == InsnID &&
+           "Mismatch between build and emit");
+    InsnMatcher->emitCaptureOpcodes(Table, Rule);
   }
 
-  void emitPredicateOpcodes(MatchTable &Table, RuleMatcher &Rule,
-                            unsigned InsnVarID_,
-                            unsigned OpIdx_) const override {
-    unsigned InsnVarID = Rule.getInsnVarID(*InsnMatcher);
-    InsnMatcher->emitPredicateOpcodes(Table, Rule, InsnVarID);
+  void emitPredicateOpcodes(MatchTable &Table,
+                            RuleMatcher &Rule) const override {
+    InsnMatcher->emitPredicateOpcodes(Table, Rule);
   }
 };
 
@@ -2188,7 +2320,9 @@
 void RuleMatcher::emitCaptureOpcodes(MatchTable &Table) {
   assert(Matchers.size() == 1 && "Cannot handle multi-root matchers yet");
   unsigned InsnVarID = implicitlyDefineInsnVar(*Matchers.front());
-  Matchers.front()->emitCaptureOpcodes(Table, *this, InsnVarID);
+  assert(Matchers.front()->getVarID() == InsnVarID &&
+         "IDs differ between build and emit");
+  Matchers.front()->emitCaptureOpcodes(Table, *this);
 }
 
 void RuleMatcher::emit(MatchTable &Table) {
@@ -2219,8 +2353,7 @@
 
   emitCaptureOpcodes(Table);
 
-  Matchers.front()->emitPredicateOpcodes(Table, *this,
-                                         getInsnVarID(*Matchers.front()));
+  Matchers.front()->emitPredicateOpcodes(Table, *this);
 
   // We must also check if it's safe to fold the matched instructions.
   if (InsnVariableIDs.size() >= 2) {
@@ -2348,11 +2481,10 @@
 }
 
 void SameOperandMatcher::emitPredicateOpcodes(MatchTable &Table,
-                                              RuleMatcher &Rule,
-                                              unsigned InsnVarID,
-                                              unsigned OpIdx) const {
+                                              RuleMatcher &Rule) const {
   const OperandMatcher &OtherOM = Rule.getOperandMatcher(MatchingName);
   unsigned OtherInsnVarID = Rule.getInsnVarID(OtherOM.getInstructionMatcher());
+  assert(OtherInsnVarID == OtherOM.getInstructionMatcher().getVarID());
 
   Table << MatchTable::Opcode("GIM_CheckIsSameOperand")
         << MatchTable::Comment("MI") << MatchTable::IntValue(InsnVarID)
@@ -2444,6 +2576,9 @@
 
   TreePatternNode *fixupPatternNode(TreePatternNode *N);
   void fixupPatternTrees(TreePattern *P);
+  std::vector<Matcher *> optimizeRules(
+      std::vector<RuleMatcher> &Rules,
+      std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher);
 };
 
 void GlobalISelEmitter::gatherNodeEquivs() {
@@ -2547,8 +2682,8 @@
         if (!MemTyOrNone)
           return failedImport("MemVT could not be converted to LLT");
 
-        InsnMatcher.getOperand(0).addPredicate<LLTOperandMatcher>(
-            MemTyOrNone.getValue());
+        OperandMatcher &OM = InsnMatcher.getOperand(0);
+        OM.addPredicate<LLTOperandMatcher>(MemTyOrNone.getValue());
         continue;
       }
     }
@@ -3144,10 +3279,34 @@
     return failedImport("Src pattern root isn't a trivial operator (" +
                         toString(std::move(Err)) + ")");
 
+  /// 1. The "predicates" are self contained, i.e., they reference
+  /// all the InsnID and OpIdx they are going to access. In
+  /// particular, they don't rely having a Rule at emission time to get
+  /// this information.
+  /// Thanks to that, we can check that two predicates are really
+  /// identical (as opposed to checking the same thing, but on
+  /// different variables).
+  ///
+  /// 2. When building the predicates we implicitly defines all the
+  /// variables that are going to be accessed in Rule
+  ///
+  /// 3. We clean the implicit def in Rule
+  ///
+  /// 4. When we emit Rule we check that the defined variables are
+  /// equal to what we chose at build time for the predicate
+  ///
+  /// FIXME: Long term, we don't want to have to rely on this implicit
+  /// naming being the same. One possible solution would be to have
+  /// explicit operator for operation capture and reference those.
+  /// The plus side is that it would expose opportunities to share
+  /// the capture accross rules. The downside is that it would
+  /// introduce a dependency between predicates (captures must happen
+  /// before their first use.)
   InstructionMatcher &InsnMatcherTemp = M.addInstructionMatcher(Src->getName());
   unsigned TempOpIdx = 0;
   auto InsnMatcherOrError =
       createAndImportSelDAGMatcher(M, InsnMatcherTemp, Src, TempOpIdx);
+  M.clearImplicitMap();
   if (auto Error = InsnMatcherOrError.takeError())
     return std::move(Error);
   InstructionMatcher &InsnMatcher = InsnMatcherOrError.get();
@@ -3354,6 +3513,38 @@
   OS << "};\n";
 }
 
+std::vector<Matcher *> GlobalISelEmitter::optimizeRules(
+    std::vector<RuleMatcher> &Rules,
+    std::vector<std::unique_ptr<GroupMatcher>> &StorageGroupMatcher) {
+  std::vector<Matcher *> OptRules;
+  // Start with a stupid grouping for now.
+  std::unique_ptr<GroupMatcher> CurrentGroup = make_unique<GroupMatcher>();
+  assert(CurrentGroup->conditions_empty());
+  unsigned NbGroup = 0;
+  for (RuleMatcher &Rule : Rules) {
+    std::unique_ptr<PredicateMatcher> Predicate = Rule.forgetFirstCondition();
+    if (!CurrentGroup->conditions_empty() &&
+        !CurrentGroup->lastConditionMatches(*Predicate)) {
+      // Start a new group.
+      ++NbGroup;
+      OptRules.push_back(CurrentGroup.get());
+      StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+      CurrentGroup = make_unique<GroupMatcher>();
+      assert(CurrentGroup->conditions_empty());
+    }
+    if (CurrentGroup->conditions_empty())
+      CurrentGroup->addCondition(std::move(Predicate));
+    CurrentGroup->addRule(Rule);
+  }
+  if (!CurrentGroup->conditions_empty()) {
+    ++NbGroup;
+    OptRules.push_back(CurrentGroup.get());
+    StorageGroupMatcher.emplace_back(std::move(CurrentGroup));
+  }
+  DEBUG(dbgs() << "NbGroup: " << NbGroup << "\n");
+  return OptRules;
+}
+
 void GlobalISelEmitter::run(raw_ostream &OS) {
   if (!UseCoverageFile.empty()) {
     RuleCoverage = CodeGenCoverage();
@@ -3404,17 +3595,6 @@
     Rules.push_back(std::move(MatcherOrErr.get()));
   }
 
-  std::stable_sort(Rules.begin(), Rules.end(),
-            [&](const RuleMatcher &A, const RuleMatcher &B) {
-              if (A.isHigherPriorityThan(B)) {
-                assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
-                                                     "and less important at "
-                                                     "the same time");
-                return true;
-              }
-              return false;
-            });
-
   std::vector<Record *> ComplexPredicates =
       RK.getAllDerivedDefinitions("GIComplexOperandMatcher");
   std::sort(ComplexPredicates.begin(), ComplexPredicates.end(),
@@ -3593,9 +3773,23 @@
      << "  State.MIs.clear();\n"
      << "  State.MIs.push_back(&I);\n\n";
 
+  std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A,
+                                                   const RuleMatcher &B) {
+    if (A.isHigherPriorityThan(B)) {
+      assert(!B.isHigherPriorityThan(A) && "Cannot be more important "
+                                           "and less important at "
+                                           "the same time");
+      return true;
+    }
+    return false;
+  });
+  std::vector<std::unique_ptr<GroupMatcher>> StorageGroupMatcher;
+
+  std::vector<Matcher *> OptRules = optimizeRules(Rules, StorageGroupMatcher);
+
   MatchTable Table(0);
-  for (auto &Rule : Rules) {
-    Rule.emit(Table);
+  for (Matcher *Rule : OptRules) {
+    Rule->emit(Table);
     ++NumPatternEmitted;
   }
   Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
@@ -3712,6 +3906,63 @@
   }
 }
 
+std::unique_ptr<PredicateMatcher> RuleMatcher::forgetFirstCondition() {
+  assert(!insnmatchers_empty() &&
+         "Trying to forget something that does not exist");
+
+  InstructionMatcher &Matcher = insnmatchers_front();
+  std::unique_ptr<PredicateMatcher> Condition;
+  if (!Matcher.predicates_empty())
+    Condition = Matcher.predicates_pop_front();
+  if (!Condition) {
+    // If there is no more predicate on the instruction itself, look at its
+    // operands.
+    assert(!Matcher.operands_empty() &&
+           "Empty instruction should have been discarded");
+    OperandMatcher &OpMatcher = **Matcher.operands_begin();
+    assert(!OpMatcher.predicates_empty() && "no operand constraint");
+    Condition = OpMatcher.predicates_pop_front();
+    // If this operand is free of constraints, rip it off.
+    if (OpMatcher.predicates_empty())
+      Matcher.pop_front();
+  }
+  // Rip the instruction off when it is empty.
+  if (Matcher.operands_empty() && Matcher.predicates_empty())
+    insnmatchers_pop_front();
+  return Condition;
+}
+
+bool GroupMatcher::lastConditionMatches(
+    const PredicateMatcher &Predicate) const {
+  const auto &LastCondition = conditions_back();
+  return Predicate.isIdentical(*LastCondition);
+}
+
+void GroupMatcher::emit(MatchTable &Table) {
+  unsigned LabelID = Table.allocateLabelID();
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Try", +1)
+          << MatchTable::Comment("On fail goto")
+          << MatchTable::JumpTarget(LabelID) << MatchTable::LineBreak;
+    for (auto &Condition : Conditions)
+      Condition->emitPredicateOpcodes(
+          Table, *static_cast<RuleMatcher *>(*Rules.begin()));
+  }
+  // Emit the conditions.
+  // Then checks apply the rules.
+  for (const auto &Rule : Rules)
+    Rule->emit(Table);
+  // If we don't succeeded for that block, that means we are not going to select
+  // this instruction.
+  if (!conditions_empty()) {
+    Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak;
+    Table << MatchTable::Opcode("GIR_Done", -1) << MatchTable::LineBreak
+          << MatchTable::Label(LabelID);
+  }
+}
+
+unsigned OperandMatcher::getInsnVarID() const { return Insn.getVarID(); }
+
 } // end anonymous namespace
 
 //===----------------------------------------------------------------------===//