Index: llvm/include/llvm/IR/PatternMatch.h
===================================================================
--- llvm/include/llvm/IR/PatternMatch.h
+++ llvm/include/llvm/IR/PatternMatch.h
@@ -50,10 +50,40 @@
   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;
+}
+
 template <typename SubPattern_t> struct OneUse_match {
   SubPattern_t SubPattern;
 
@@ -958,6 +988,7 @@
 struct BinaryOp_match {
   LHS_t L;
   RHS_t R;
+  bool IsOneUse = false;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
@@ -978,7 +1009,18 @@
     return false;
   }
 
-  template <typename OpTy> bool match(OpTy *V) { return match(Opcode, V); }
+  template <typename OpTy> bool match(OpTy *V) {
+    if (match(Opcode, V)) {
+      IsOneUse = V->hasOneUse();
+      return true;
+    }
+    return false;
+  }
+
+  unsigned getUseComplexity() const {
+    return (IsOneUse ? 0 : 1) + getMatchUseComplexity(L) +
+           getMatchUseComplexity(R);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1232,7 +1274,11 @@
       : 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);
+    if (BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::match(Opcode, V)) {
+      BinaryOp_match<LHS_t, RHS_t, 0, Commutable>::IsOneUse = V->hasOneUse();
+      return true;
+    }
+    return false;
   }
 };
 
Index: llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -1728,22 +1728,25 @@
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C;
+  int UseComplexity;
 
   // (~(A | B) & C) | ... --> ...
   // (~(A & B) | C) & ... --> ...
   // TODO: One use checks are conservative. We just need to check that a total
   //       number of multiple used values does not exceed reduction
   //       in operations.
-  if (match(Op0, m_c_BinOp(FlippedOpcode,
-                           m_Not(m_BinOp(Opcode, m_Value(A), m_Value(B))),
-                           m_Value(C)))) {
+  if (match(Op0,
+            m_c_BinOp(FlippedOpcode,
+                      m_Not(m_BinOp(Opcode, m_Value(A), m_Value(B))),
+                      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))