Index: llvm/include/llvm/IR/PatternMatch.h
===================================================================
--- llvm/include/llvm/IR/PatternMatch.h
+++ llvm/include/llvm/IR/PatternMatch.h
@@ -50,10 +50,73 @@
   return const_cast<Pattern &>(P).match(V);
 }
 
+/// Match Value \p V against Pattern \P. Store a number of matched operations
+/// with multiple uses into \p UseComplexity if provided. Match fails if the
+/// complexity is higher than MaxComplexity.
+template <typename Val, typename Pattern>
+bool match(Val *V, const Pattern &P, int *UseComplexity,
+           int MaxComplexity = INT_MAX) {
+  if (MaxComplexity < 0 || !const_cast<Pattern &>(P).match(V))
+    return false;
+  int Complexity = (int)P.getUseComplexity();
+  if (UseComplexity)
+    *UseComplexity = Complexity;
+  return Complexity <= MaxComplexity;
+}
+
 template <typename Pattern> bool match(ArrayRef<int> Mask, const Pattern &P) {
   return const_cast<Pattern &>(P).match(Mask);
 }
 
+template <typename T>
+using has_get_use_complexity_t =
+    decltype(std::declval<T &>().getUseComplexity());
+
+template <typename T>
+std::enable_if_t<is_detected<has_get_use_complexity_t, T>::value, unsigned>
+getMatchUseComplexity(T V) {
+  return V.getUseComplexity();
+}
+
+template <typename T>
+std::enable_if_t<!is_detected<has_get_use_complexity_t, T>::value, unsigned>
+getMatchUseComplexity(T V) {
+  return 0;
+}
+
+struct ValueUseTracker {
+  bool IsOneUse = false;
+
+  template <typename OpTy> void trackUse(OpTy *V) {
+    IsOneUse = V->hasOneUse();
+  }
+
+  template <typename OpTy> bool trackUse(OpTy *V, bool Match) {
+    if (Match)
+      trackUse(V);
+    return Match;
+  }
+
+  unsigned getUseComplexity() const {
+    return IsOneUse ? 0 : 1;
+  }
+};
+
+template <typename T0, typename T1 = T0, typename T2 = T0>
+struct UseTracker : ValueUseTracker {
+  unsigned getUseComplexity(T0 Op) const {
+    return ValueUseTracker::getUseComplexity() + getMatchUseComplexity(Op);
+  }
+
+  unsigned getUseComplexity(T0 Op0, T1 Op1) const {
+    return getUseComplexity(Op0) + getMatchUseComplexity(Op1);
+  }
+
+  unsigned getUseComplexity(T0 Op0, T1 Op1, T2 Op2) const {
+    return getUseComplexity(Op1) + getMatchUseComplexity(Op2);
+  }
+};
+
 template <typename SubPattern_t> struct OneUse_match {
   SubPattern_t SubPattern;
 
@@ -179,16 +242,25 @@
 template <typename LTy, typename RTy> struct match_combine_or {
   LTy L;
   RTy R;
+  bool IsLeft = false;
 
   match_combine_or(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
 
   template <typename ITy> bool match(ITy *V) {
-    if (L.match(V))
+    if (L.match(V)) {
+      IsLeft = true;
       return true;
-    if (R.match(V))
+    }
+    if (R.match(V)) {
+      IsLeft = false;
       return true;
+    }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return IsLeft ? getMatchUseComplexity(L) : getMatchUseComplexity(R);
+  }
 };
 
 template <typename LTy, typename RTy> struct match_combine_and {
@@ -203,6 +275,10 @@
         return true;
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return std::max(getMatchUseComplexity(L), getMatchUseComplexity(R));
+  }
 };
 
 /// Combine two pattern matchers matching L || R
@@ -715,19 +791,34 @@
   }
 };
 
+template <typename Class>
+struct inst_bind_ty : bind_ty<Class>, UseTracker<Class> {
+  inst_bind_ty(Class *&V) : bind_ty<Class>(V) {}
+
+  template <typename ITy> bool match(ITy *V) {
+    return ValueUseTracker::trackUse(V, bind_ty<Class>::match(V));
+  }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<Class>::getUseComplexity(bind_ty<Class>::VR);
+  }
+};
+
 /// Match a value, capturing it if we match.
 inline bind_ty<Value> m_Value(Value *&V) { return V; }
 inline bind_ty<const Value> m_Value(const Value *&V) { return V; }
 
 /// Match an instruction, capturing it if we match.
-inline bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
+inline inst_bind_ty<Instruction> m_Instruction(Instruction *&I) { return I; }
 /// Match a unary operator, capturing it if we match.
-inline bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
+inline inst_bind_ty<UnaryOperator> m_UnOp(UnaryOperator *&I) { return I; }
 /// Match a binary operator, capturing it if we match.
-inline bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
+inline inst_bind_ty<BinaryOperator> m_BinOp(BinaryOperator *&I) { return I; }
 /// Match a with overflow intrinsic, capturing it if we match.
-inline bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) { return I; }
-inline bind_ty<const WithOverflowInst>
+inline inst_bind_ty<WithOverflowInst> m_WithOverflowInst(WithOverflowInst *&I) {
+  return I;
+}
+inline inst_bind_ty<const WithOverflowInst>
 m_WithOverflowInst(const WithOverflowInst *&I) {
   return I;
 }
@@ -907,7 +998,7 @@
 // Matcher for any binary operator.
 //
 template <typename LHS_t, typename RHS_t, bool Commutable = false>
-struct AnyBinaryOp_match {
+struct AnyBinaryOp_match : UseTracker<LHS_t, RHS_t> {
   LHS_t L;
   RHS_t R;
 
@@ -917,11 +1008,16 @@
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<BinaryOperator>(V))
-      return (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
-             (Commutable && L.match(I->getOperand(1)) &&
-              R.match(I->getOperand(0)));
+      return ValueUseTracker::trackUse(
+          V, ((L.match(I->getOperand(0)) && R.match(I->getOperand(1))) ||
+              (Commutable && L.match(I->getOperand(1)) &&
+               R.match(I->getOperand(0)))));
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -933,16 +1029,21 @@
 // Matcher for any unary operator.
 // TODO fuse unary, binary matcher into n-ary matcher
 //
-template <typename OP_t> struct AnyUnaryOp_match {
+template <typename OP_t> struct AnyUnaryOp_match : UseTracker<OP_t> {
   OP_t X;
 
   AnyUnaryOp_match(const OP_t &X) : X(X) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    if (auto *I = dyn_cast<UnaryOperator>(V))
-      return X.match(I->getOperand(0));
+    if (auto *I = dyn_cast<UnaryOperator>(V)) {
+      return ValueUseTracker::trackUse(V, X.match(I->getOperand(0)));
+    }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<OP_t>::getMatchUseComplexity(X);
+  }
 };
 
 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
@@ -955,7 +1056,7 @@
 
 template <typename LHS_t, typename RHS_t, unsigned Opcode,
           bool Commutable = false>
-struct BinaryOp_match {
+struct BinaryOp_match : UseTracker<LHS_t, RHS_t> {
   LHS_t L;
   RHS_t R;
 
@@ -978,7 +1079,13 @@
     return false;
   }
 
-  template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
+  template <typename OpTy> bool match(OpTy *V) {
+    return ValueUseTracker::trackUse(V, match(Opcode, V));
+  }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1005,7 +1112,7 @@
   return BinaryOp_match<LHS, RHS, Instruction::FSub>(L, R);
 }
 
-template <typename Op_t> struct FNeg_match {
+template <typename Op_t> struct FNeg_match : UseTracker<Op_t> {
   Op_t X;
 
   FNeg_match(const Op_t &Op) : X(Op) {}
@@ -1014,7 +1121,7 @@
     if (!FPMO) return false;
 
     if (FPMO->getOpcode() == Instruction::FNeg)
-      return X.match(FPMO->getOperand(0));
+      return ValueUseTracker::trackUse(V, X.match(FPMO->getOperand(0)));
 
     if (FPMO->getOpcode() == Instruction::FSub) {
       if (FPMO->hasNoSignedZeros()) {
@@ -1027,11 +1134,15 @@
           return false;
       }
 
-      return X.match(FPMO->getOperand(1));
+      return ValueUseTracker::trackUse(V, X.match(FPMO->getOperand(1)));
     }
 
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<Op_t>::getMatchUseComplexity(X);
+  }
 };
 
 /// Match 'fneg X' as 'fsub -0.0, X'.
@@ -1134,7 +1245,7 @@
 
 template <typename LHS_t, typename RHS_t, unsigned Opcode,
           unsigned WrapFlags = 0>
-struct OverflowingBinaryOp_match {
+struct OverflowingBinaryOp_match : UseTracker<LHS_t, RHS_t> {
   LHS_t L;
   RHS_t R;
 
@@ -1151,10 +1262,15 @@
       if ((WrapFlags & OverflowingBinaryOperator::NoSignedWrap) &&
           !Op->hasNoSignedWrap())
         return false;
-      return L.match(Op->getOperand(0)) && R.match(Op->getOperand(1));
+      return ValueUseTracker::trackUse(V, L.match(Op->getOperand(0)) &&
+                                              R.match(Op->getOperand(1)));
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1232,7 +1348,8 @@
       : BinaryOp_match<LHS_t, RHS_t, 0, Commutable>(LHS, RHS), Opcode(Opcode) {}
 
   template <typename OpTy> bool match(OpTy *V) {
-    return BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V);
+    return ValueUseTracker::trackUse(
+        V, BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V));
   }
 };
 
@@ -1247,7 +1364,7 @@
 // Class that matches a group of binary opcodes.
 //
 template <typename LHS_t, typename RHS_t, typename Predicate>
-struct BinOpPred_match : Predicate {
+struct BinOpPred_match : Predicate, UseTracker<LHS_t, RHS_t> {
   LHS_t L;
   RHS_t R;
 
@@ -1255,13 +1372,19 @@
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<Instruction>(V))
-      return this->isOpType(I->getOpcode()) && L.match(I->getOperand(0)) &&
-             R.match(I->getOperand(1));
+      return ValueUseTracker::trackUse(V, this->isOpType(I->getOpcode()) &&
+                                              L.match(I->getOperand(0)) &&
+                                              R.match(I->getOperand(1)));
     if (auto *CE = dyn_cast<ConstantExpr>(V))
-      return this->isOpType(CE->getOpcode()) && L.match(CE->getOperand(0)) &&
-             R.match(CE->getOperand(1));
+      return ValueUseTracker::trackUse(V, this->isOpType(CE->getOpcode()) &&
+                                              L.match(CE->getOperand(0)) &&
+                                              R.match(CE->getOperand(1)));
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 struct is_shift_op {
@@ -1353,6 +1476,10 @@
       return PEO->isExact() && SubPattern.match(V);
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return SubPattern.getUseComplexity();
+  }
 };
 
 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
@@ -1365,7 +1492,7 @@
 
 template <typename LHS_t, typename RHS_t, typename Class, typename PredicateTy,
           bool Commutable = false>
-struct CmpClass_match {
+struct CmpClass_match : UseTracker<LHS_t, RHS_t> {
   PredicateTy &Predicate;
   LHS_t L;
   RHS_t R;
@@ -1379,15 +1506,21 @@
     if (auto *I = dyn_cast<Class>(V)) {
       if (L.match(I->getOperand(0)) && R.match(I->getOperand(1))) {
         Predicate = I->getPredicate();
+        ValueUseTracker::trackUse(V);
         return true;
       } else if (Commutable && L.match(I->getOperand(1)) &&
            R.match(I->getOperand(0))) {
         Predicate = I->getSwappedPredicate();
+        ValueUseTracker::trackUse(V);
         return true;
       }
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1413,7 +1546,7 @@
 //
 
 /// Matches instructions with Opcode and three operands.
-template <typename T0, unsigned Opcode> struct OneOps_match {
+template <typename T0, unsigned Opcode> struct OneOps_match : UseTracker<T0> {
   T0 Op1;
 
   OneOps_match(const T0 &Op1) : Op1(Op1) {}
@@ -1421,14 +1554,19 @@
   template <typename OpTy> bool match(OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opcode) {
       auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0));
+      return ValueUseTracker::trackUse(V, Op1.match(I->getOperand(0)));
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<T0>::getUseComplexity(Op1);
+  }
 };
 
 /// Matches instructions with Opcode and three operands.
-template <typename T0, typename T1, unsigned Opcode> struct TwoOps_match {
+template <typename T0, typename T1, unsigned Opcode>
+struct TwoOps_match : UseTracker<T0, T1> {
   T0 Op1;
   T1 Op2;
 
@@ -1437,15 +1575,19 @@
   template <typename OpTy> bool match(OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opcode) {
       auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1));
-    }
+      return ValueUseTracker::trackUse(V, Op1.match(I->getOperand(0)) &&
+                                              Op2.match(I->getOperand(1)));    }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<T0, T1>::getUseComplexity(Op1, Op2);
+  }
 };
 
 /// Matches instructions with Opcode and three operands.
 template <typename T0, typename T1, typename T2, unsigned Opcode>
-struct ThreeOps_match {
+struct ThreeOps_match : UseTracker<T0, T1, T2> {
   T0 Op1;
   T1 Op2;
   T2 Op3;
@@ -1456,11 +1598,16 @@
   template <typename OpTy> bool match(OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opcode) {
       auto *I = cast<Instruction>(V);
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
-             Op3.match(I->getOperand(2));
+      return ValueUseTracker::trackUse(V, Op1.match(I->getOperand(0)) &&
+                                              Op2.match(I->getOperand(1)) &&
+                                              Op3.match(I->getOperand(2)));
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<T0, T1, T2>::getUseComplexity(Op1, Op2, Op3);
+  }
 };
 
 /// Matches SelectInst.
@@ -1501,7 +1648,8 @@
 }
 
 /// Matches shuffle.
-template <typename T0, typename T1, typename T2> struct Shuffle_match {
+template <typename T0, typename T1, typename T2>
+struct Shuffle_match : UseTracker<T0, T1, T2> {
   T0 Op1;
   T1 Op2;
   T2 Mask;
@@ -1511,11 +1659,16 @@
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<ShuffleVectorInst>(V)) {
-      return Op1.match(I->getOperand(0)) && Op2.match(I->getOperand(1)) &&
-             Mask.match(I->getShuffleMask());
+      return ValueUseTracker::trackUse(V, Op1.match(I->getOperand(0)) &&
+                                              Op2.match(I->getOperand(1)) &&
+                                              Mask.match(I->getShuffleMask()));
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<T0, T1, T2>::getUseComplexity(Op1, Op2, Mask);
+  }
 };
 
 struct m_Mask {
@@ -1583,16 +1736,22 @@
 // Matchers for CastInst classes
 //
 
-template <typename Op_t, unsigned Opcode> struct CastClass_match {
+template <typename Op_t, unsigned Opcode>
+struct CastClass_match : UseTracker<Op_t> {
   Op_t Op;
 
   CastClass_match(const Op_t &OpMatch) : Op(OpMatch) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *O = dyn_cast<Operator>(V))
-      return O->getOpcode() == Opcode && Op.match(O->getOperand(0));
+      return ValueUseTracker::trackUse(V, O->getOpcode() == Opcode &&
+                                              Op.match(O->getOperand(0)));
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<Op_t>::getUseComplexity(Op);
+  }
 };
 
 /// Matches BitCast.
@@ -1752,7 +1911,7 @@
 
 template <typename CmpInst_t, typename LHS_t, typename RHS_t, typename Pred_t,
           bool Commutable = false>
-struct MaxMin_match {
+struct MaxMin_match : UseTracker<LHS_t, RHS_t> {
   using PredType = Pred_t;
   LHS_t L;
   RHS_t R;
@@ -1769,8 +1928,9 @@
           (IID == Intrinsic::umax && Pred_t::match(ICmpInst::ICMP_UGT)) ||
           (IID == Intrinsic::umin && Pred_t::match(ICmpInst::ICMP_ULT))) {
         Value *LHS = II->getOperand(0), *RHS = II->getOperand(1);
-        return (L.match(LHS) && R.match(RHS)) ||
-               (Commutable && L.match(RHS) && R.match(LHS));
+        return ValueUseTracker::trackUse(
+            V, (L.match(LHS) && R.match(RHS)) ||
+                   (Commutable && L.match(RHS) && R.match(LHS)));
       }
     }
     // Look for "(x pred y) ? x : y" or "(x pred y) ? y : x".
@@ -1795,8 +1955,13 @@
     if (!Pred_t::match(Pred))
       return false;
     // It does!  Bind the operands.
-    return (L.match(LHS) && R.match(RHS)) ||
-           (Commutable && L.match(RHS) && R.match(LHS));
+    return ValueUseTracker::trackUse(
+        V, (L.match(LHS) && R.match(RHS)) ||
+               (Commutable && L.match(RHS) && R.match(LHS)));
+  }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
   }
 };
 
@@ -1957,7 +2122,7 @@
 //
 
 template <typename LHS_t, typename RHS_t, typename Sum_t>
-struct UAddWithOverflow_match {
+struct UAddWithOverflow_match : UseTracker<LHS_t, RHS_t> {
   LHS_t L;
   RHS_t R;
   Sum_t S;
@@ -1965,7 +2130,7 @@
   UAddWithOverflow_match(const LHS_t &L, const RHS_t &R, const Sum_t &S)
       : L(L), R(R), S(S) {}
 
-  template <typename OpTy> bool match(OpTy *V) {
+  template <typename OpTy> bool match_impl(OpTy *V) {
     Value *ICmpLHS, *ICmpRHS;
     ICmpInst::Predicate Pred;
     if (!m_ICmp(Pred, m_Value(ICmpLHS), m_Value(ICmpRHS)).match(V))
@@ -2013,6 +2178,14 @@
 
     return false;
   }
+
+  template <typename OpTy> bool match(OpTy *V) {
+    return ValueUseTracker::trackUse(V, match_impl(V));
+  }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 /// Match an icmp instruction checking for unsigned overflow on addition.
@@ -2285,7 +2458,7 @@
   return m_c_Xor(V, m_AllOnes());
 }
 
-template <typename ValTy> struct NotForbidUndef_match {
+template <typename ValTy> struct NotForbidUndef_match : UseTracker<ValTy> {
   ValTy Val;
   NotForbidUndef_match(const ValTy &V) : Val(V) {}
 
@@ -2296,11 +2469,15 @@
     Value *X;
     const APInt *C;
     if (m_Xor(m_Value(X), m_APIntForbidUndef(C)).match(V) && C->isAllOnes())
-      return Val.match(X);
+      return ValueUseTracker::trackUse(V, Val.match(X));
     if (m_Xor(m_APIntForbidUndef(C), m_Value(X)).match(V) && C->isAllOnes())
-      return Val.match(X);
+      return ValueUseTracker::trackUse(V, Val.match(X));
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<ValTy>::getUseComplexity(Val);
+  }
 };
 
 /// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
@@ -2360,7 +2537,7 @@
   return BinaryOp_match<LHS, RHS, Instruction::FMul, true>(L, R);
 }
 
-template <typename Opnd_t> struct Signum_match {
+template <typename Opnd_t> struct Signum_match : UseTracker<Opnd_t> {
   Opnd_t Val;
   Signum_match(const Opnd_t &V) : Val(V) {}
 
@@ -2386,7 +2563,12 @@
     auto RHS = m_LShr(m_Neg(m_Value(OpR)), m_SpecificInt(ShiftWidth));
     auto Signum = m_Or(LHS, RHS);
 
-    return Signum.match(V) && OpL == OpR && Val.match(OpL);
+    return ValueUseTracker::trackUse(V, Signum.match(V) && OpL == OpR &&
+                                            Val.match(OpL));
+  }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<Opnd_t>::getUseComplexity(Val);
   }
 };
 
@@ -2400,7 +2582,8 @@
   return Signum_match<Val_t>(V);
 }
 
-template <int Ind, typename Opnd_t> struct ExtractValue_match {
+template <int Ind, typename Opnd_t>
+struct ExtractValue_match : UseTracker<Opnd_t> {
   Opnd_t Val;
   ExtractValue_match(const Opnd_t &V) : Val(V) {}
 
@@ -2410,10 +2593,14 @@
       if (Ind != -1 &&
           !(I->getNumIndices() == 1 && I->getIndices()[0] == (unsigned)Ind))
         return false;
-      return Val.match(I->getAggregateOperand());
+      return ValueUseTracker::trackUse(V, Val.match(I->getAggregateOperand()));
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<Opnd_t>::getUseComplexity(Val);
+  }
 };
 
 /// Match a single index ExtractValue instruction.
@@ -2431,7 +2618,8 @@
 }
 
 /// Matcher for a single index InsertValue instruction.
-template <int Ind, typename T0, typename T1> struct InsertValue_match {
+template <int Ind, typename T0, typename T1>
+struct InsertValue_match : UseTracker<T0, T1>{
   T0 Op0;
   T1 Op1;
 
@@ -2439,11 +2627,16 @@
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<InsertValueInst>(V)) {
-      return Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
-             I->getNumIndices() == 1 && Ind == I->getIndices()[0];
+      return ValueUseTracker::trackUse(
+          V, Op0.match(I->getOperand(0)) && Op1.match(I->getOperand(1)) &&
+                 I->getNumIndices() == 1 && Ind == I->getIndices()[0]);
     }
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<T0, T1>::getUseComplexity(Op0, Op1);
+  }
 };
 
 /// Matches a single index InsertValue instruction.
@@ -2486,7 +2679,7 @@
 }
 
 template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
-struct LogicalOp_match {
+struct LogicalOp_match : UseTracker<LHS, RHS> {
   LHS L;
   RHS R;
 
@@ -2500,8 +2693,9 @@
     if (I->getOpcode() == Opcode) {
       auto *Op0 = I->getOperand(0);
       auto *Op1 = I->getOperand(1);
-      return (L.match(Op0) && R.match(Op1)) ||
-             (Commutable && L.match(Op1) && R.match(Op0));
+      return ValueUseTracker::trackUse(
+          V, (L.match(Op0) && R.match(Op1)) ||
+                 (Commutable && L.match(Op1) && R.match(Op0)));
     }
 
     if (auto *Select = dyn_cast<SelectInst>(I)) {
@@ -2511,19 +2705,25 @@
       if (Opcode == Instruction::And) {
         auto *C = dyn_cast<Constant>(FVal);
         if (C && C->isNullValue())
-          return (L.match(Cond) && R.match(TVal)) ||
-                 (Commutable && L.match(TVal) && R.match(Cond));
+          return ValueUseTracker::trackUse(
+              V, (L.match(Cond) && R.match(TVal)) ||
+                     (Commutable && L.match(TVal) && R.match(Cond)));
       } else {
         assert(Opcode == Instruction::Or);
         auto *C = dyn_cast<Constant>(TVal);
         if (C && C->isOneValue())
-          return (L.match(Cond) && R.match(FVal)) ||
-                 (Commutable && L.match(FVal) && R.match(Cond));
+          return ValueUseTracker::trackUse(
+              V, (L.match(Cond) && R.match(FVal)) ||
+                     (Commutable && L.match(FVal) && R.match(Cond)));
       }
     }
 
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS, RHS>::getUseComplexity(L, R);
+  }
 };
 
 /// Matches L && R either in the form of L & R or L ? R : false.
Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1728,6 +1728,7 @@
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C, *X, *Y;
+  int UseComplexity;
 
   // (~(A | B) & C) | ... --> ...
   // (~(A & B) | C) & ... --> ...
@@ -1738,14 +1739,15 @@
             m_c_BinOp(FlippedOpcode,
                       m_CombineAnd(m_Value(X), m_Not(m_BinOp(Opcode, m_Value(A),
                                                              m_Value(B)))),
-                      m_Value(C)))) {
+                      m_Value(C)),
+            &UseComplexity)) {
     // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
     // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
     if (match(Op1,
-              m_OneUse(m_c_BinOp(FlippedOpcode,
-                                 m_OneUse(m_Not(m_c_BinOp(Opcode, m_Specific(A),
-                                                          m_Specific(C)))),
-                                 m_Specific(B))))) {
+              m_c_BinOp(FlippedOpcode,
+                        m_Not(m_c_BinOp(Opcode, m_Specific(A), m_Specific(C))),
+                        m_Specific(B)),
+              nullptr, 4 - UseComplexity)) {
       Value *Xor = Builder.CreateXor(B, C);
       return (Opcode == Instruction::Or)
                  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
Index: llvm/test/Transforms/InstCombine/and-xor-or.ll
===================================================================
--- llvm/test/Transforms/InstCombine/and-xor-or.ll
+++ llvm/test/Transforms/InstCombine/and-xor-or.ll
@@ -914,13 +914,11 @@
 
 define i32 @or_not_and_extra_not_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @or_not_and_extra_not_use2(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -959,13 +957,12 @@
 
 define i32 @or_not_and_extra_and_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @or_not_and_extra_and_use2(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -1020,6 +1017,210 @@
   ret i32 %or3
 }
 
+define i32 @or_not_and_4_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_4_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+;  call void @use(i32 %and1)
+
+  call void @use(i32 %or2)
+;  call void @use(i32 %not2)
+  call void @use(i32 %and2)
+;  call void @use(i32 %or3)
+  ret i32 %or3
+}
+
+define i32 @or_not_and_4_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_4_uses2(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+  call void @use(i32 %and1)
+
+  call void @use(i32 %or2)
+  call void @use(i32 %and2)
+  ret i32 %or3
+}
+
+define i32 @or_not_and_4_uses3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_4_uses3(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @or_not_and_5_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_5_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %and1)
+
+  call void @use(i32 %or2)
+  call void @use(i32 %and2)
+  ret i32 %or3
+}
+
+define i32 @or_not_and_5_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_5_uses2(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[AND2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+  call void @use(i32 %and1)
+
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  call void @use(i32 %and2)
+  ret i32 %or3
+}
+
+define i32 @or_not_and_5_uses3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_5_uses3(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = and i32 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR3]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %a, %b
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %c
+
+  %or2 = or i32 %a, %c
+  %not2 = xor i32 %or2, -1
+  %and2 = and i32 %not2, %b
+  %or3 = or i32 %and1, %and2
+
+  call void @use(i32 %or1)
+
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  call void @use(i32 %and2)
+  call void @use(i32 %or3)
+  ret i32 %or3
+}
+
 define i32 @or_not_and_wrong_c(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @or_not_and_wrong_c(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[A:%.*]], [[B:%.*]]
@@ -1277,13 +1478,11 @@
 
 define i32 @and_not_or_extra_not_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @and_not_or_extra_not_use2(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B:%.*]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
@@ -1322,13 +1521,12 @@
 
 define i32 @and_not_or_extra_and_use2(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @and_not_or_extra_and_use2(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT1]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;