Index: llvm/include/llvm/IR/PatternMatch.h
===================================================================
--- llvm/include/llvm/IR/PatternMatch.h
+++ llvm/include/llvm/IR/PatternMatch.h
@@ -50,10 +50,75 @@
   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(false);
+  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(std::declval<bool>()));
+
+template <typename T>
+std::enable_if_t<is_detected<has_get_use_complexity_t, T>::value, unsigned>
+getMatchUseComplexity(T V, bool Used) {
+  return V.getUseComplexity(Used);
+}
+
+template <typename T>
+std::enable_if_t<!is_detected<has_get_use_complexity_t, T>::value, unsigned>
+getMatchUseComplexity(T V, bool Used) {
+  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(bool Used) const {
+    return (IsOneUse && !Used) ? 0 : 1;
+  }
+};
+
+template <typename T0, typename T1 = T0, typename T2 = T0>
+struct UseTracker : ValueUseTracker {
+  unsigned getUseComplexity(T0 Op, bool Used) const {
+    Used |= !ValueUseTracker::IsOneUse;
+    return ValueUseTracker::getUseComplexity(Used) +
+           getMatchUseComplexity(Op, Used);
+  }
+
+  unsigned getUseComplexity(T0 Op0, T1 Op1, bool Used) const {
+    Used |= !ValueUseTracker::IsOneUse;
+    return getUseComplexity(Op0, Used) + getMatchUseComplexity(Op1, Used);
+  }
+
+  unsigned getUseComplexity(T0 Op0, T1 Op1, T2 Op2, bool Used) const {
+    Used |= !ValueUseTracker::IsOneUse;
+    return getUseComplexity(Op1, Used) + getMatchUseComplexity(Op2, Used);
+  }
+};
+
 template <typename SubPattern_t> struct OneUse_match {
   SubPattern_t SubPattern;
 
@@ -179,16 +244,26 @@
 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(bool Used) const {
+    return IsLeft ? getMatchUseComplexity(L, Used)
+                  : getMatchUseComplexity(R, Used);
+  }
 };
 
 template <typename LTy, typename RTy> struct match_combine_and {
@@ -203,6 +278,11 @@
         return true;
     return false;
   }
+
+  unsigned getUseComplexity(bool Used) const {
+    return std::max(getMatchUseComplexity(L, Used),
+                    getMatchUseComplexity(R, Used));
+  }
 };
 
 /// Combine two pattern matchers matching L || R
@@ -718,19 +798,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(bool Used) const {
+    return UseTracker<Class>::getUseComplexity(bind_ty<Class>::VR, Used);
+  }
+};
+
 /// 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;
 }
@@ -910,7 +1005,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;
 
@@ -920,11 +1015,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -936,16 +1036,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(bool Used) const {
+    return UseTracker<OP_t>::getMatchUseComplexity(X, Used);
+  }
 };
 
 template <typename OP_t> inline AnyUnaryOp_match<OP_t> m_UnOp(const OP_t &X) {
@@ -958,7 +1063,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;
 
@@ -981,7 +1086,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1008,7 +1119,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) {}
@@ -1017,7 +1128,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()) {
@@ -1030,11 +1141,15 @@
           return false;
       }
 
-      return X.match(FPMO->getOperand(1));
+      return ValueUseTracker::trackUse(V, X.match(FPMO->getOperand(1)));
     }
 
     return false;
   }
+
+  unsigned getUseComplexity(bool Used) const {
+    return UseTracker<Op_t>::getMatchUseComplexity(X, Used);
+  }
 };
 
 /// Match 'fneg X' as 'fsub -0.0, X'.
@@ -1137,7 +1252,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;
 
@@ -1154,10 +1269,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1235,7 +1355,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));
   }
 };
 
@@ -1250,7 +1371,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;
 
@@ -1258,13 +1379,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 struct is_shift_op {
@@ -1356,6 +1483,10 @@
       return PEO->isExact() && SubPattern.match(V);
     return false;
   }
+
+  unsigned getUseComplexity(bool Used) const {
+    return SubPattern.getUseComplexity(Used);
+  }
 };
 
 template <typename T> inline Exact_match<T> m_Exact(const T &SubPattern) {
@@ -1368,7 +1499,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;
@@ -1382,15 +1513,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 template <typename LHS, typename RHS>
@@ -1416,7 +1553,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) {}
@@ -1424,14 +1561,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(bool Used) const {
+    return UseTracker<T0>::getUseComplexity(Op1, Used);
+  }
 };
 
 /// 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;
 
@@ -1440,15 +1582,20 @@
   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(bool Used) const {
+    return UseTracker<T0, T1>::getUseComplexity(Op1, Op2, Used);
+  }
 };
 
 /// 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;
@@ -1459,11 +1606,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(bool Used) const {
+    return UseTracker<T0, T1, T2>::getUseComplexity(Op1, Op2, Op3, Used);
+  }
 };
 
 /// Matches SelectInst.
@@ -1504,7 +1656,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;
@@ -1514,11 +1667,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(bool Used) const {
+    return UseTracker<T0, T1, T2>::getUseComplexity(Op1, Op2, Mask, Used);
+  }
 };
 
 struct m_Mask {
@@ -1586,16 +1744,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(bool Used) const {
+    return UseTracker<Op_t>::getUseComplexity(Op, Used);
+  }
 };
 
 /// Matches BitCast.
@@ -1755,7 +1919,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;
@@ -1772,8 +1936,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".
@@ -1798,8 +1963,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(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
   }
 };
 
@@ -1960,7 +2130,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;
@@ -1968,7 +2138,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))
@@ -2016,6 +2186,14 @@
 
     return false;
   }
+
+  template <typename OpTy> bool match(OpTy *V) {
+    return ValueUseTracker::trackUse(V, match_impl(V));
+  }
+
+  unsigned getUseComplexity(bool Used) const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R, Used);
+  }
 };
 
 /// Match an icmp instruction checking for unsigned overflow on addition.
@@ -2288,7 +2466,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) {}
 
@@ -2299,11 +2477,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(bool Used) const {
+    return UseTracker<ValTy>::getUseComplexity(Val, Used);
+  }
 };
 
 /// Matches a bitwise 'not' as 'xor V, -1' or 'xor -1, V'. For vectors, the
@@ -2363,7 +2545,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) {}
 
@@ -2389,7 +2571,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(bool Used) const {
+    return UseTracker<Opnd_t>::getUseComplexity(Val, Used);
   }
 };
 
@@ -2403,7 +2590,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) {}
 
@@ -2413,10 +2601,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(bool Used) const {
+    return UseTracker<Opnd_t>::getUseComplexity(Val, Used);
+  }
 };
 
 /// Match a single index ExtractValue instruction.
@@ -2434,7 +2626,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;
 
@@ -2442,11 +2635,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(bool Used) const {
+    return UseTracker<T0, T1>::getUseComplexity(Op0, Op1, Used);
+  }
 };
 
 /// Matches a single index InsertValue instruction.
@@ -2489,7 +2687,7 @@
 }
 
 template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
-struct LogicalOp_match {
+struct LogicalOp_match : UseTracker<LHS, RHS> {
   LHS L;
   RHS R;
 
@@ -2503,8 +2701,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)) {
@@ -2514,19 +2713,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(bool Used) const {
+    return UseTracker<LHS, RHS>::getUseComplexity(L, R, Used);
+  }
 };
 
 /// 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, *Dummy;
+  int UseComplexity;
 
   // Match following expressions:
   // (~(A | B) & C)
@@ -1735,17 +1736,14 @@
   // Captures X = ~(A | B) or ~(A & B)
   const auto matchNotOrAnd =
       [Opcode, FlippedOpcode](Value *Op, auto m_A, auto m_B, auto m_C,
-                              Value *&X, bool CountUses = false) -> bool {
-    if (CountUses && !Op->hasOneUse())
-      return false;
-
-    if (match(Op, m_c_BinOp(FlippedOpcode,
-                            m_CombineAnd(m_Value(X),
-                                         m_Not(m_c_BinOp(Opcode, m_A, m_B))),
-                            m_C)))
-      return !CountUses || X->hasOneUse();
-
-    return false;
+                              Value *&X, int *UseComplexity,
+                              int MaxComplexity = INT_MAX) -> bool {
+    return match(
+        Op,
+        m_c_BinOp(FlippedOpcode,
+                  m_CombineAnd(m_Value(X), m_Not(m_c_BinOp(Opcode, m_A, m_B))),
+                  m_C),
+        UseComplexity, MaxComplexity);
   };
 
   // (~(A | B) & C) | ... --> ...
@@ -1753,11 +1751,12 @@
   // 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 (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X)) {
+  if (matchNotOrAnd(Op0, m_Value(A), m_Value(B), m_Value(C), X,
+                    &UseComplexity)) {
     // (~(A | B) & C) | (~(A | C) & B) --> (B ^ C) & ~A
     // (~(A & B) | C) & (~(A & C) | B) --> ~((B ^ C) & A)
     if (matchNotOrAnd(Op1, m_Specific(A), m_Specific(C), m_Specific(B), Dummy,
-                      true)) {
+                      nullptr, 4 - UseComplexity)) {
       Value *Xor = Builder.CreateXor(B, C);
       return (Opcode == Instruction::Or)
                  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(A))
@@ -1767,7 +1766,7 @@
     // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
     // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)
     if (matchNotOrAnd(Op1, m_Specific(B), m_Specific(C), m_Specific(A), Dummy,
-                      true)) {
+                      nullptr, 4 - UseComplexity)) {
       Value *Xor = Builder.CreateXor(A, C);
       return (Opcode == Instruction::Or)
                  ? BinaryOperator::CreateAnd(Xor, Builder.CreateNot(B))
@@ -1776,15 +1775,15 @@
 
     // (~(A | B) & C) | ~(A | C) --> ~((B & C) | A)
     // (~(A & B) | C) & ~(A & C) --> ~((B | C) & A)
-    if (match(Op1, m_OneUse(m_Not(m_OneUse(
-                       m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
+    if (match(Op1, m_Not(m_c_BinOp(Opcode, m_Specific(A), m_Specific(C))),
+              nullptr, 3 - UseComplexity))
       return BinaryOperator::CreateNot(Builder.CreateBinOp(
           Opcode, Builder.CreateBinOp(FlippedOpcode, B, C), A));
 
     // (~(A | B) & C) | ~(B | C) --> ~((A & C) | B)
     // (~(A & B) | C) & ~(B & C) --> ~((A | C) & B)
-    if (match(Op1, m_OneUse(m_Not(m_OneUse(
-                       m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)))))))
+    if (match(Op1, m_Not(m_c_BinOp(Opcode, m_Specific(B), m_Specific(C))),
+              nullptr, 3 - UseComplexity))
       return BinaryOperator::CreateNot(Builder.CreateBinOp(
           Opcode, Builder.CreateBinOp(FlippedOpcode, A, C), B));
 
@@ -1792,11 +1791,13 @@
     // Note, the pattern with swapped and/or is not handled because the
     // result is more undefined than a source:
     // (~(A & B) | C) & ~(C & (A ^ B)) --> (A ^ B ^ C) | ~(A | C) is invalid.
-    if (Opcode == Instruction::Or && Op0->hasOneUse() &&
-        match(Op1, m_OneUse(m_Not(m_CombineAnd(
-                       m_Value(Y),
-                       m_c_BinOp(Opcode, m_Specific(C),
-                                 m_c_Xor(m_Specific(A), m_Specific(B)))))))) {
+    if (Opcode == Instruction::Or &&
+        match(
+            Op1,
+            m_Not(m_CombineAnd(
+                m_Value(Y), m_c_BinOp(Opcode, m_Specific(C),
+                                      m_c_Xor(m_Specific(A), m_Specific(B))))),
+            nullptr, 5 - UseComplexity)) {
       // X = ~(A | B)
       // Y = (C | (A ^ B)
       Value *Or = cast<BinaryOperator>(X)->getOperand(0);
@@ -1806,30 +1807,35 @@
 
   // (~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_OneUse(m_c_BinOp(FlippedOpcode,
-                               m_BinOp(FlippedOpcode, m_Value(B), m_Value(C)),
-                               m_CombineAnd(m_Value(X), m_Not(m_Value(A)))))) ||
-      match(Op0, m_OneUse(m_c_BinOp(
-                     FlippedOpcode,
-                     m_c_BinOp(FlippedOpcode, m_Value(C),
-                               m_CombineAnd(m_Value(X), m_Not(m_Value(A)))),
-                     m_Value(B))))) {
+            m_c_BinOp(FlippedOpcode,
+                      m_BinOp(FlippedOpcode, m_Value(B), m_Value(C)),
+                      m_CombineAnd(m_Value(X), m_Not(m_Value(A)))),
+            &UseComplexity) ||
+      match(Op0,
+            m_c_BinOp(FlippedOpcode,
+                      m_c_BinOp(FlippedOpcode, m_Value(C),
+                                m_CombineAnd(m_Value(X), m_Not(m_Value(A)))),
+                      m_Value(B)),
+            &UseComplexity)) {
     // X = ~A
     // (~A & B & C) | ~(A | B | C) --> ~(A | (B ^ C))
     // (~A | B | C) & ~(A & B & C) --> (~A | (B ^ C))
-    if (match(Op1, m_OneUse(m_Not(m_c_BinOp(
-                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)),
-                       m_Specific(C))))) ||
-        match(Op1, m_OneUse(m_Not(m_c_BinOp(
-                       Opcode, m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
-                       m_Specific(A))))) ||
-        match(Op1, m_OneUse(m_Not(m_c_BinOp(
-                       Opcode, m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
-                       m_Specific(B)))))) {
+    if (match(Op1,
+              m_Not(m_c_BinOp(Opcode,
+                              m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)),
+                              m_Specific(C))),
+              nullptr, 5 - UseComplexity) ||
+        match(Op1,
+              m_Not(m_c_BinOp(Opcode,
+                              m_c_BinOp(Opcode, m_Specific(B), m_Specific(C)),
+                              m_Specific(A))),
+              nullptr, 5 - UseComplexity) ||
+        match(Op1,
+              m_Not(m_c_BinOp(Opcode,
+                              m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)),
+                              m_Specific(B))),
+              nullptr, 5 - UseComplexity)) {
       Value *Xor = Builder.CreateXor(B, C);
       return (Opcode == Instruction::Or)
                  ? BinaryOperator::CreateNot(Builder.CreateOr(Xor, A))
@@ -1838,16 +1844,16 @@
 
     // (~A & B & C) | ~(A | B) --> (C | ~B) & ~A
     // (~A | B | C) & ~(A & B) --> (C & ~B) | ~A
-    if (match(Op1, m_OneUse(m_Not(m_OneUse(
-                       m_c_BinOp(Opcode, m_Specific(A), m_Specific(B)))))))
+    if (match(Op1, m_Not(m_c_BinOp(Opcode, m_Specific(A), m_Specific(B))),
+              nullptr, 3 - UseComplexity))
       return BinaryOperator::Create(
           FlippedOpcode, Builder.CreateBinOp(Opcode, C, Builder.CreateNot(B)),
           X);
 
     // (~A & B & C) | ~(A | C) --> (B | ~C) & ~A
     // (~A | B | C) & ~(A & C) --> (B & ~C) | ~A
-    if (match(Op1, m_OneUse(m_Not(m_OneUse(
-                       m_c_BinOp(Opcode, m_Specific(A), m_Specific(C)))))))
+    if (match(Op1, m_Not(m_c_BinOp(Opcode, m_Specific(A), m_Specific(C))),
+              nullptr, 3 - UseComplexity))
       return BinaryOperator::Create(
           FlippedOpcode, Builder.CreateBinOp(Opcode, B, Builder.CreateNot(C)),
           X);
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,233 @@
   ret i32 %or3
 }
 
+; Even though there are only 2 uses all the instructions have to remain
+; since used values are outermost subexpressions.
+define i32 @or_not_and_2_uses_rhs_and_lhs(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_not_and_2_uses_rhs_and_lhs(
+; 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 [[AND1]])
+; 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 %and1)
+  call void @use(i32 %and2)
+  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:    [[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 [[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 %or2)
+  call void @use(i32 %and2)
+  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:    [[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 [[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 +1501,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 +1544,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]]
 ;
@@ -1383,6 +1604,126 @@
   ret i32 %and3
 }
 
+define i32 @and_not_or_4_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_4_uses1(
+; 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:    [[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 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %a, %b
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %not1, %c
+  %and2 = and i32 %a, %c
+  %not2 = xor i32 %and2, -1
+  %or2 = or i32 %not2, %b
+  %and3 = and i32 %or1, %or2
+  call void @use(i32 %and1)
+  call void @use(i32 %not1)
+  call void @use(i32 %or1)
+  call void @use(i32 %and2)
+  ret i32 %and3
+}
+
+define i32 @and_not_or_4_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_4_uses2(
+; 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:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %a, %b
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %not1, %c
+  %and2 = and i32 %a, %c
+  %not2 = xor i32 %and2, -1
+  %or2 = or i32 %not2, %b
+  %and3 = and i32 %or1, %or2
+  call void @use(i32 %not1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  ret i32 %and3
+}
+
+define i32 @and_not_or_5_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_5_uses1(
+; 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:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %a, %b
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %not1, %c
+  %and2 = and i32 %a, %c
+  %not2 = xor i32 %and2, -1
+  %or2 = or i32 %not2, %b
+  %and3 = and i32 %or1, %or2
+  call void @use(i32 %and1)
+  call void @use(i32 %not1)
+  call void @use(i32 %or1)
+  call void @use(i32 %and2)
+  call void @use(i32 %not2)
+  ret i32 %and3
+}
+
+define i32 @and_not_or_5_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_5_uses2(
+; 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:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %a, %b
+  %not1 = xor i32 %and1, -1
+  %or1 = or i32 %not1, %c
+  %and2 = and i32 %a, %c
+  %not2 = xor i32 %and2, -1
+  %or2 = or i32 %not2, %b
+  %and3 = and i32 %or1, %or2
+  call void @use(i32 %and1)
+  call void @use(i32 %not1)
+  call void @use(i32 %or1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or2)
+  ret i32 %and3
+}
+
 define i32 @and_not_or_wrong_c(i32 %a, i32 %b, i32 %c, i32 %d) {
 ; CHECK-LABEL: @and_not_or_wrong_c(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[A:%.*]], [[B:%.*]]
@@ -1563,10 +1904,9 @@
 ; CHECK-LABEL: @or_and_not_not_extra_not_use1(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -1621,14 +1961,12 @@
   ret i32 %or3
 }
 
-define i32 @or_and_not_not_extra_or_use1(i32 %a, i32 %b, i32 %c) {
-; CHECK-LABEL: @or_and_not_not_extra_or_use1(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND]], [[NOT1]]
+define i32 @or_and_not_not_extra_or_use1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @or_and_not_not_extra_or_use1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -1661,8 +1999,7 @@
   ret i32 %or3
 }
 
-; Check the use limit. It can be adjusted in the future in terms of
-; LHS and RHS uses distribution to be more flexible.
+; Check the use limit.
 define i32 @or_and_not_not_2_extra_uses(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @or_and_not_not_2_extra_uses(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
@@ -1862,10 +2199,9 @@
 ; CHECK-LABEL: @and_or_not_not_extra_not_use1(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
@@ -1923,10 +2259,9 @@
 define i32 @and_or_not_not_extra_or_use1(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @and_or_not_not_extra_or_use1(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[A]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[AND2]], -1
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND1]], [[OR]]
+; CHECK-NEXT:    [[TMP1:%.*]] = or i32 [[C:%.*]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
@@ -2188,8 +2523,8 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -2249,12 +2584,253 @@
 define i32 @and_not_or_or_not_or_xor_use6(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @and_not_or_or_not_or_xor_use6(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_4_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_4_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %not1)
+  call void @use(i32 %and1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses2(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %and1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses3(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses3(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses4(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses4(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; 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 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  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)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses5(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses5(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; 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 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %and1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %not2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_5_uses6(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_5_uses6(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[OR1]], [[OR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP1]], -1
+; 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 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %or1 = or i32 %b, %c
+  %not1 = xor i32 %or1, -1
+  %and1 = and i32 %not1, %a
+  %xor1 = xor i32 %b, %c
+  %or2 = or i32 %xor1, %a
+  %not2 = xor i32 %or2, -1
+  %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %and1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
+  ret i32 %or3
+}
+
+define i32 @and_not_or_or_not_or_xor_6_uses(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @and_not_or_or_not_or_xor_6_uses(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[A:%.*]]
 ; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[C]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[A]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND1]], [[NOT2]]
+; 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 [[XOR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -2265,6 +2841,11 @@
   %or2 = or i32 %xor1, %a
   %not2 = xor i32 %or2, -1
   %or3 = or i32 %and1, %not2
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %and1)
+  call void @use(i32 %xor1)
+  call void @use(i32 %or2)
   call void @use(i32 %not2)
   ret i32 %or3
 }
@@ -2737,10 +3318,9 @@
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -2798,13 +3378,12 @@
 
 define i32 @not_and_and_or_not_or_or_use6(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_not_or_or_use6(
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR2]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C]]
-; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[A]]
+; CHECK-NEXT:    [[OR3:%.*]] = xor i32 [[TMP2]], -1
 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
 ; CHECK-NEXT:    ret i32 [[OR3]]
 ;
@@ -3027,9 +3606,8 @@
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
-; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
@@ -3085,12 +3663,129 @@
 
 define i32 @not_or_or_and_not_and_and_use6(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_not_and_and_use6(
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %b, %a
+  %and2 = and i32 %and1, %c
+  %not1 = xor i32 %and2, -1
+  %not2 = xor i32 %a, -1
+  %or1 = or i32 %not2, %b
+  %or2 = or i32 %or1, %c
+  %and3 = and i32 %or2, %not1
+  call void @use(i32 %or2)
+  ret i32 %and3
+}
+
+define i32 @not_or_or_and_not_and_and_4_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_or_and_not_and_and_4_uses1(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %b, %a
+  %and2 = and i32 %and1, %c
+  %not1 = xor i32 %and2, -1
+  %not2 = xor i32 %a, -1
+  %or1 = or i32 %not2, %b
+  %or2 = or i32 %or1, %c
+  %and3 = and i32 %or2, %not1
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  ret i32 %and3
+}
+
+define i32 @not_or_or_and_not_and_and_5_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_or_and_not_and_and_5_uses1(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[C]], [[B]]
+; CHECK-NEXT:    [[AND3:%.*]] = or i32 [[TMP1]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %b, %a
+  %and2 = and i32 %and1, %c
+  %not1 = xor i32 %and2, -1
+  %not2 = xor i32 %a, -1
+  %or1 = or i32 %not2, %b
+  %or2 = or i32 %or1, %c
+  %and3 = and i32 %or2, %not1
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  call void @use(i32 %or1)
+  ret i32 %and3
+}
+
+define i32 @not_or_or_and_not_and_and_5_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_or_and_not_and_and_5_uses2(
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
+; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[AND3]]
+;
+  %and1 = and i32 %b, %a
+  %and2 = and i32 %and1, %c
+  %not1 = xor i32 %and2, -1
+  %not2 = xor i32 %a, -1
+  %or1 = or i32 %not2, %b
+  %or2 = or i32 %or1, %c
+  %and3 = and i32 %or2, %not1
+  call void @use(i32 %and2)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  call void @use(i32 %or1)
+  call void @use(i32 %or2)
+  ret i32 %and3
+}
+
+define i32 @not_or_or_and_not_and_and_6_uses(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_or_or_and_not_and_and_6_uses(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND2]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C]]
 ; CHECK-NEXT:    [[AND3:%.*]] = xor i32 [[AND2]], [[OR2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    ret i32 [[AND3]]
 ;
@@ -3101,6 +3796,11 @@
   %or1 = or i32 %not2, %b
   %or2 = or i32 %or1, %c
   %and3 = and i32 %or2, %not1
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  call void @use(i32 %or1)
   call void @use(i32 %or2)
   ret i32 %and3
 }
@@ -3292,11 +3992,10 @@
 define i32 @not_and_and_or_no_or_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_no_or_use5(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[OR1]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
@@ -3315,9 +4014,9 @@
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
@@ -3353,12 +4052,113 @@
 
 define i32 @not_and_and_or_no_or_use8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_and_and_or_no_or_use8(
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %not2 = xor i32 %a, -1
+  %and1 = and i32 %not2, %b
+  %and2 = and i32 %and1, %c
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %and2)
+  ret i32 %or2
+}
+
+define i32 @not_and_and_or_no_or_3_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_and_or_no_or_3_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %not2 = xor i32 %a, -1
+  %and1 = and i32 %not2, %b
+  %and2 = and i32 %and1, %c
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  ret i32 %or2
+}
+
+define i32 @not_and_and_or_no_or_3_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_and_or_no_or_3_uses2(
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = or i32 [[TMP1]], [[C]]
+; CHECK-NEXT:    [[OR2:%.*]] = and i32 [[TMP2]], [[NOT2]]
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    call void @use(i32 [[AND2]])
+; CHECK-NEXT:    call void @use(i32 [[OR2]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %not2 = xor i32 %a, -1
+  %and1 = and i32 %not2, %b
+  %and2 = and i32 %and1, %c
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %and1)
+  call void @use(i32 %and2)
+  call void @use(i32 %or2)
+  ret i32 %or2
+}
+
+define i32 @not_and_and_or_no_or_4_uses1(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_and_or_no_or_4_uses1(
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
+; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
+; CHECK-NEXT:    call void @use(i32 [[AND1]])
+; CHECK-NEXT:    ret i32 [[OR2]]
+;
+  %or1 = or i32 %b, %a
+  %not1 = xor i32 %or1, -1
+  %not2 = xor i32 %a, -1
+  %and1 = and i32 %not2, %b
+  %and2 = and i32 %and1, %c
+  %or2 = or i32 %and2, %not1
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
+  call void @use(i32 %and1)
+  ret i32 %or2
+}
+
+define i32 @not_and_and_or_no_or_4_uses2(i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: @not_and_and_or_no_or_4_uses2(
 ; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT2]], [[B]]
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[AND1]], [[C:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[AND2]], [[NOT1]]
+; CHECK-NEXT:    call void @use(i32 [[OR1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT1]])
+; CHECK-NEXT:    call void @use(i32 [[NOT2]])
 ; CHECK-NEXT:    call void @use(i32 [[AND2]])
 ; CHECK-NEXT:    ret i32 [[OR2]]
 ;
@@ -3368,6 +4168,9 @@
   %and1 = and i32 %not2, %b
   %and2 = and i32 %and1, %c
   %or2 = or i32 %and2, %not1
+  call void @use(i32 %or1)
+  call void @use(i32 %not1)
+  call void @use(i32 %not2)
   call void @use(i32 %and2)
   ret i32 %or2
 }
@@ -3559,11 +4362,10 @@
 define i32 @not_or_or_and_no_and_use5(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_no_and_use5(
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[AND1]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
@@ -3582,9 +4384,9 @@
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
-; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C:%.*]]
+; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[NOT1]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;
@@ -3620,12 +4422,12 @@
 
 define i32 @not_or_or_and_no_and_use8(i32 %a, i32 %b, i32 %c) {
 ; CHECK-LABEL: @not_or_or_and_no_and_use8(
-; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[AND1]], -1
-; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B]]
+; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[A:%.*]], -1
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 [[NOT2]], [[B:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[OR1]], [[C:%.*]]
-; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[OR2]], [[NOT1]]
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[B]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[C]]
+; CHECK-NEXT:    [[AND2:%.*]] = or i32 [[TMP2]], [[NOT2]]
 ; CHECK-NEXT:    call void @use(i32 [[OR2]])
 ; CHECK-NEXT:    ret i32 [[AND2]]
 ;