[PatternMatch] Create match method to track uses complexity

[rampitec]

Summary

This patch introduces new match function which can return
a number of matched operations with multiple uses. It also
can take an argument with a limit of such operands number
for match to succeed.

The function is needed if we want to limit a total number
of multiply used operands but do not necessarily care which.

[lebedev.ri]

I'm somewhat unconvinced that we can solve this problem at the match stage.
Consider

v0 = a + c
v1 = v0 + c
v2 = v1 + c
r = v2 + c

if you do match(m_Add(m_Add(m_Add(m_Add(m_Value(A), m_Value(C)), m_Specific(C)), m_Specific(C)), m_Specific(C))),
i think UseComplexity will be 4(?), but that doesn't mean that you can create 4 instructions,
in reality it depends on the pattern you will produce. If you want to produce a + 4*c, sure, you can do that,
because none of the instructions you matched are used in the pattern. But if you want to produce
v2 + 1*c, you can not, because that would increase instruction count...

[rampitec]

In D114126#3139528, @lebedev.ri wrote:

I'm somewhat unconvinced that we can solve this problem at the match stage.
Consider

v0 = a + c
v1 = v0 + c
v2 = v1 + c
r = v2 + c

if you do match(m_Add(m_Add(m_Add(m_Add(m_Value(A), m_Value(C)), m_Specific(C)), m_Specific(C)), m_Specific(C))),
i think UseComplexity will be 4(?), but that doesn't mean that you can create 4 instructions,
in reality it depends on the pattern you will produce. If you want to produce a + 4*c, sure, you can do that,
because none of the instructions you matched are used in the pattern. But if you want to produce
v2 + 1*c, you can not, because that would increase instruction count...

In that match complexity will be zero because none of the values have more than one use. Than you can rule what is your complexity to use as a limit based on your target transform, just like I did in the example transform with 4 instructions being a threshold just on the grounds of comparing source and target code.

The assumption is that all that instructions go away after transform except those which have uses outside of the source pattern. And then even if not you can adjust the limit. I guess I will have to do it where I am reusing a subexpression, because a reused value shall not count, it just stays, but that needs a proper handling of m_CombineAnd as a max of complexity of its operands, which I have not done yet. Then speaking of that m_CombineOr shall use a complexity of a selected leg.

[rampitec]

A side note: I have initially tried to modify match() methods to accept and calculate complexity arguments and being stateless, just return them. I have then realized that turns into nightmare because a match can restart and retry, and that is nearly impossible to track statelessly. The benefit was obvious: an early termination of a match, but the accounting cost quickly became too high and not stateless anyway. That said I believe only a BinOp and UnOp will have to keep state. Well, combine and/or too likely. The leaf matches like m_Value or constants do not count and have complexity zero anyway. So the new match interface will have to sum final complexity after the whole match has succeeded and states recorded.

[rampitec]

Use SFINAE to only add getUseComplexity() method to matchers which really need it. This will be much less code than previously anticipated.

[nikic]

Taking a step back here, I want to ask: Is this solving some kind of real problem? I get the impression that use counting in InstCombine has moved beyond a practical consideration into the realm of religious dogma. I don't think there is much value in always making exotic, complex folds maximally applicable in multi-use scenarios, if doing so does not happen to be straightforward.

[rampitec]

In D114126#3140943, @nikic wrote:

Taking a step back here, I want to ask: Is this solving some kind of real problem? I get the impression that use counting in InstCombine has moved beyond a practical consideration into the realm of religious dogma. I don't think there is much value in always making exotic, complex folds maximally applicable in multi-use scenarios, if doing so does not happen to be straightforward.

The example use is one application, the rest of the cases in the same function too. In fact in a later experiments I came across a situation when we do not perform reassociation in the demorganing bacause of the multi use issue and I have a hard time solving it without such accounting.

The other practical improvement is that it shall just simplify the accounting. It is easier to write something like 4 - UseComplexity and omit all m_OneUse than counting unwrapped patterns.

[rampitec]

The patch is ready now.

[rampitec]

This is actually a bad idea at least as is. A use of an subexpression will preserve the whole subexpression which needs to be accounted in the complexity.

[rampitec]

• Fixed subexpression cost handling, any use at root now marks each value in subexpression used.
• Changed all patterns foldComplexAndOrPatterns.
• Added tests.

[rampitec]

Rebased.
Added handling of newly added case (~A & B & C) | ~(A | B) --> (C | ~B) & ~A.

[rampitec]

ping

[rampitec]

Rebased.

[spatel]

I'm not opposed to the direction, but I don't have enough C++ knowledge to review the implementation.

@nikic commented on the exactness of use counting that we've created and wondered if we need to try so hard. I sympathize/agree with that view.
But I've actually hoped that we could loosen the constraints on some patterns - that is, allow the creation of more instructions because the transform is still beneficial from an overall use count.
Take for example one of the motivating Demorgan patterns for this patch:
https://alive2.llvm.org/ce/z/4XGCm3
The 'not' ops have extra uses, so we don't do: (~A & ~B) --> ~(A | B) even though that would get the final result in 2 ops instead of 3. But we don't do the inverse transform either (it requires more than simple pattern-matching).
If we removed some strictness about uses, we probably wouldn't require this patch or the follow-ons for complicated bitwise logic optimizations. Those are only needed because we miss the simpler, intermediate folds in complex expressions with extra uses. I suppose we'd be more at risk for infinite combine loops if we allowed creating extra instructions, but it might be worth experimenting with removing some use checks on bitwise logic folds to see how that plays out.

[rampitec]

In D114126#3227404, @spatel wrote:

If we removed some strictness about uses, we probably wouldn't require this patch or the follow-ons for complicated bitwise logic optimizations. Those are only needed because we miss the simpler, intermediate folds in complex expressions with extra uses. I suppose we'd be more at risk for infinite combine loops if we allowed creating extra instructions, but it might be worth experimenting with removing some use checks on bitwise logic folds to see how that plays out.

More than infinite loops (which is also possible) I am worried we may in fact make code worse without taking into account a wider pattern.
Anyhow, we used to discuss this approach in the very beginning of the ternary changes stack, so I thought to give it a try. It turns out to be more complicated change than I was initially anticipated unfortunately. I am not pushing this in any way.

[rampitec]

I am going to abandon this and all other instcombine changes due to the lack of interest.

llvm/include/llvm/IR/PatternMatch.h

 
 namespace llvm {
 namespace PatternMatch {
 
 template <typename Val, typename Pattern> bool match(Val *V, const Pattern &P) {
   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;
 
   OneUse_match(const SubPattern_t &SP) : SubPattern(SP) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     return V->hasOneUse() && SubPattern.match(V);
   }

 template <typename Ty> inline match_unless<Ty> m_Unless(const Ty &M) {
   return match_unless<Ty>(M);
 }
 
 /// Matching combinators
 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 {
   LTy L;
   RTy R;
 
   match_combine_and(const LTy &Left, const RTy &Right) : L(Left), R(Right) {}
 
   template <typename ITy> bool match(ITy *V) {
     if (L.match(V))
       if (R.match(V))
         return true;
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return std::max(getMatchUseComplexity(L), getMatchUseComplexity(R));
+  }
 };
 
 /// Combine two pattern matchers matching L || R
 template <typename LTy, typename RTy>
 inline match_combine_or<LTy, RTy> m_CombineOr(const LTy &L, const RTy &R) {
   return match_combine_or<LTy, RTy>(L, R);
 }
 
template <typename ITy> bool match(ITy *V) {
     if (auto *CV = dyn_cast<Class>(V)) {
       VR = CV;
       return true;
     }
     return false;
   }
 };
 
+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;
 }
 
 /// Match a Constant, capturing the value if we match.
 inline bind_ty<Constant> m_Constant(Constant *&C) { return C; }
 
 /// Match a ConstantInt, capturing the value if we match.

 m_Deferred(const BasicBlock *const &BB) {
   return BB;
 }
 
 //===----------------------------------------------------------------------===//
 // 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;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   AnyBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   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))) ||
+      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)));
+               R.match(I->getOperand(0)))));
     return false;
   }
+
+  unsigned getUseComplexity() const {
+    return UseTracker<LHS_t, RHS_t>::getUseComplexity(L, R);
+  }
 };
 
 template <typename LHS, typename RHS>
 inline AnyBinaryOp_match<LHS, RHS> m_BinOp(const LHS &L, const RHS &R) {
   return AnyBinaryOp_match<LHS, RHS>(L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // 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) {
   return AnyUnaryOp_match<OP_t>(X);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for specific binary operators.
 //
 
 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;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   BinaryOp_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> inline bool match(unsigned Opc, OpTy *V) {
     if (V->getValueID() == Value::InstructionVal + Opc) {
       auto *I = 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)));
     }
     if (auto *CE = dyn_cast<ConstantExpr>(V))
       return CE->getOpcode() == Opc &&
              ((L.match(CE->getOperand(0)) && R.match(CE->getOperand(1))) ||
               (Commutable && L.match(CE->getOperand(1)) &&
                R.match(CE->getOperand(0))));
     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>
 inline BinaryOp_match<LHS, RHS, Instruction::Add> m_Add(const LHS &L,
                                                         const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::Add>(L, R);
 }
 

 }
 
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::FSub> m_FSub(const LHS &L,
                                                           const RHS &R) {
   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) {}
   template <typename OpTy> bool match(OpTy *V) {
     auto *FPMO = dyn_cast<FPMathOperator>(V);
     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()) {
         // With 'nsz', any zero goes.
         if (!cstfp_pred_ty<is_any_zero_fp>().match(FPMO->getOperand(0)))
           return false;
       } else {
         // Without 'nsz', we need fsub -0.0, X exactly.
         if (!cstfp_pred_ty<is_neg_zero_fp>().match(FPMO->getOperand(0)))
           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'.
 template <typename OpTy>
 inline FNeg_match<OpTy>
 m_FNeg(const OpTy &X) {
   return FNeg_match<OpTy>(X);
 }

 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::AShr> m_AShr(const LHS &L,
                                                           const RHS &R) {
   return BinaryOp_match<LHS, RHS, Instruction::AShr>(L, R);
 }
 
 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;
 
   OverflowingBinaryOp_match(const LHS_t &LHS, const RHS_t &RHS)
       : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *Op = dyn_cast<OverflowingBinaryOperator>(V)) {
       if (Op->getOpcode() != Opcode)
         return false;
       if ((WrapFlags & OverflowingBinaryOperator::NoUnsignedWrap) &&
           !Op->hasNoUnsignedWrap())
         return false;
       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>
 inline OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
                                  OverflowingBinaryOperator::NoSignedWrap>
 m_NSWAdd(const LHS &L, const RHS &R) {
   return OverflowingBinaryOp_match<LHS, RHS, Instruction::Add,
                                    OverflowingBinaryOperator::NoSignedWrap>(

 struct SpecificBinaryOp_match
     : public BinaryOp_match<LHS_t, RHS_t, 0, Commutable> {
   unsigned Opcode;
 
   SpecificBinaryOp_match(unsigned Opcode, const LHS_t &LHS, const RHS_t &RHS)
       : 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));
   }
 };
 
 /// Matches a specific opcode.
 template <typename LHS, typename RHS>
 inline SpecificBinaryOp_match<LHS, RHS> m_BinOp(unsigned Opcode, const LHS &L,
                                                 const RHS &R) {
   return SpecificBinaryOp_match<LHS, RHS>(Opcode, L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // 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;
 
   BinOpPred_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   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 {
   bool isOpType(unsigned Opcode) { return Instruction::isShift(Opcode); }
 };
 
 struct is_right_shift_op {
   bool isOpType(unsigned Opcode) {
template <typename SubPattern_t> struct Exact_match {
 
   Exact_match(const SubPattern_t &SP) : SubPattern(SP) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *PEO = dyn_cast<PossiblyExactOperator>(V))
       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) {
   return SubPattern;
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for CmpInst classes
 //
 
 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;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   CmpClass_match(PredicateTy &Pred, const LHS_t &LHS, const RHS_t &RHS)
       : Predicate(Pred), L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     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>
 inline CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>
 m_Cmp(CmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
   return CmpClass_match<LHS, RHS, CmpInst, CmpInst::Predicate>(Pred, L, R);
 }
 
m_FCmp(FCmpInst::Predicate &Pred, const LHS &L, const RHS &R) {
   return CmpClass_match<LHS, RHS, FCmpInst, FCmpInst::Predicate>(Pred, L, R);
 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for instructions with a given opcode and number of operands.
 //
 
 /// 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) {}
 
   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;
 
   TwoOps_match(const T0 &Op1, const T1 &Op2) : Op1(Op1), Op2(Op2) {}
 
   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;
 
   ThreeOps_match(const T0 &Op1, const T1 &Op2, const T2 &Op3)
       : Op1(Op1), Op2(Op2), Op3(Op3) {}
 
   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.
 template <typename Cond, typename LHS, typename RHS>
 inline ThreeOps_match<Cond, LHS, RHS, Instruction::Select>
 m_Select(const Cond &C, const LHS &L, const RHS &R) {
   return ThreeOps_match<Cond, LHS, RHS, Instruction::Select>(C, L, R);
 }

 /// Matches ExtractElementInst.
 template <typename Val_t, typename Idx_t>
 inline TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>
 m_ExtractElt(const Val_t &Val, const Idx_t &Idx) {
   return TwoOps_match<Val_t, Idx_t, Instruction::ExtractElement>(Val, Idx);
 }
 
 /// 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;
 
   Shuffle_match(const T0 &Op1, const T1 &Op2, const T2 &Mask)
       : Op1(Op1), Op2(Op2), Mask(Mask) {}
 
   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 {
   ArrayRef<int> &MaskRef;
   m_Mask(ArrayRef<int> &MaskRef) : MaskRef(MaskRef) {}
   bool match(ArrayRef<int> Mask) {
     MaskRef = Mask;
     return true;
m_Store(const ValueOpTy &ValueOp, const PointerOpTy &PointerOp) {
   return TwoOps_match<ValueOpTy, PointerOpTy, Instruction::Store>(ValueOp,
                                                                   PointerOp);
 }
 
 //===----------------------------------------------------------------------===//
 // 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.
 template <typename OpTy>
 inline CastClass_match<OpTy, Instruction::BitCast> m_BitCast(const OpTy &Op) {
   return CastClass_match<OpTy, Instruction::BitCast>(Op);
 }
 

 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for max/min idioms, eg: "select (sgt x, y), x, y" -> smax(x,y).
 //
 
 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;
 
   // The evaluation order is always stable, regardless of Commutability.
   // The LHS is always matched first.
   MaxMin_match(const LHS_t &LHS, const RHS_t &RHS) : L(LHS), R(RHS) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *II = dyn_cast<IntrinsicInst>(V)) {
       Intrinsic::ID IID = II->getIntrinsicID();
       if ((IID == Intrinsic::smax && Pred_t::match(ICmpInst::ICMP_SGT)) ||
           (IID == Intrinsic::smin && Pred_t::match(ICmpInst::ICMP_SLT)) ||
           (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".
     auto *SI = dyn_cast<SelectInst>(V);
     if (!SI)
       return false;
     auto *Cmp = dyn_cast<CmpInst_t>(SI->getCondition());
     if (!Cmp)
       return false;
     // At this point we have a select conditioned on a comparison.  Check that
     // it is the values returned by the select that are being compared.
     auto *TrueVal = SI->getTrueValue();
     auto *FalseVal = SI->getFalseValue();
     auto *LHS = Cmp->getOperand(0);
     auto *RHS = Cmp->getOperand(1);
     if ((TrueVal != LHS || FalseVal != RHS) &&
         (TrueVal != RHS || FalseVal != LHS))
       return false;
     typename CmpInst_t::Predicate Pred =
         LHS == TrueVal ? Cmp->getPredicate() : Cmp->getInversePredicate();
     // Does "(x pred y) ? x : y" represent the desired max/min operation?
     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);
   }
 };
 
 /// Helper class for identifying signed max predicates.
 struct smax_pred_ty {
   static bool match(ICmpInst::Predicate Pred) {
     return Pred == CmpInst::ICMP_SGT || Pred == CmpInst::ICMP_SGE;
   }

 }
 
 //===----------------------------------------------------------------------===//
 // Matchers for overflow check patterns: e.g. (a + b) u< a, (a ^ -1) <u b
 // Note that S might be matched to other instructions than AddInst.
 //
 
 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;
 
   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))
       return false;
 
     Value *AddLHS, *AddRHS;
     auto AddExpr = m_Add(m_Value(AddLHS), m_Value(AddRHS));
 
if (Pred == ICmpInst::ICMP_EQ) {
       // 0 == (1 + a)
       if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
           (m_One().match(AddLHS) || m_One().match(AddRHS)))
         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
     }
 
     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.
 ///
 /// S is matched to the addition whose result is being checked for overflow, and
 /// L and R are matched to the LHS and RHS of S.
 template <typename LHS_t, typename RHS_t, typename Sum_t>
 UAddWithOverflow_match<LHS_t, RHS_t, Sum_t>

 
 /// Matches a 'Not' as 'xor V, -1' or 'xor -1, V'.
 template <typename ValTy>
 inline BinaryOp_match<ValTy, cst_pred_ty<is_all_ones>, Instruction::Xor, true>
 m_Not(const ValTy &V) {
   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) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     // We do not use m_c_Xor because that could match an arbitrary APInt that is
     // not -1 as C and then fail to match the other operand if it is -1.
     // This code should still work even when both operands are constants.
     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
 /// constant value must be composed of only -1 scalar elements.
 template <typename ValTy>
 inline NotForbidUndef_match<ValTy> m_NotForbidUndef(const ValTy &V) {
   return NotForbidUndef_match<ValTy>(V);
 }

 
 /// Matches FMul with LHS and RHS in either order.
 template <typename LHS, typename RHS>
 inline BinaryOp_match<LHS, RHS, Instruction::FMul, true>
 m_c_FMul(const LHS &L, const RHS &R) {
   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) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     unsigned TypeSize = V->getType()->getScalarSizeInBits();
     if (TypeSize == 0)
       return false;
 
template <typename OpTy> bool match(OpTy *V) {
     //  signum(x) == (x >> 0)  | (-x >>u 0)
     //
     // for i1 values.
 
     auto LHS = m_AShr(m_Value(OpL), m_SpecificInt(ShiftWidth));
     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);
   }
 };
 
 /// Matches a signum pattern.
 ///
 /// signum(x) =
 ///      x >  0  ->  1
 ///      x == 0  ->  0
 ///      x <  0  -> -1
 template <typename Val_t> inline Signum_match<Val_t> m_Signum(const Val_t &V) {
   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) {}
 
   template <typename OpTy> bool match(OpTy *V) {
     if (auto *I = dyn_cast<ExtractValueInst>(V)) {
       // If Ind is -1, don't inspect indices
       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.
 /// For example m_ExtractValue<1>(...)
 template <int Ind, typename Val_t>
 inline ExtractValue_match<Ind, Val_t> m_ExtractValue(const Val_t &V) {
   return ExtractValue_match<Ind, Val_t>(V);
 }
 
 /// Match an ExtractValue instruction with any index.
 /// For example m_ExtractValue(...)
 template <typename Val_t>
 inline ExtractValue_match<-1, Val_t> m_ExtractValue(const Val_t &V) {
   return ExtractValue_match<-1, Val_t>(V);
 }
 
 /// 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;
 
   InsertValue_match(const T0 &Op0, const T1 &Op1) : Op0(Op0), Op1(Op1) {}
 
   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.
 template <int Ind, typename Val_t, typename Elt_t>
 inline InsertValue_match<Ind, Val_t, Elt_t> m_InsertValue(const Val_t &Val,
                                                           const Elt_t &Elt) {
   return InsertValue_match<Ind, Val_t, Elt_t>(Val, Elt);
 }
struct VScaleVal_match {
   }
 };
 
 inline VScaleVal_match m_VScale(const DataLayout &DL) {
   return VScaleVal_match(DL);
 }
 
 template <typename LHS, typename RHS, unsigned Opcode, bool Commutable = false>
-struct LogicalOp_match {
+struct LogicalOp_match : UseTracker<LHS, RHS> {
   LHS L;
   RHS R;
 
   LogicalOp_match(const LHS &L, const RHS &R) : L(L), R(R) {}
 
   template <typename T> bool match(T *V) {
     auto *I = dyn_cast<Instruction>(V);
     if (!I || !I->getType()->isIntOrIntVectorTy(1))
       return false;
 
     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)) {
       auto *Cond = Select->getCondition();
       auto *TVal = Select->getTrueValue();
       auto *FVal = Select->getFalseValue();
       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.
 /// Note that the latter form is poison-blocking.
 template <typename LHS, typename RHS>
 inline LogicalOp_match<LHS, RHS, Instruction::And>
 m_LogicalAnd(const LHS &L, const RHS &R) {
   return LogicalOp_match<LHS, RHS, Instruction::And>(L, R);

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

static Instruction *foldComplexAndOrPatterns(BinaryOperator &I,
   assert(Opcode == Instruction::And || Opcode == Instruction::Or);
 
   // Flip the logic operation.
   const Instruction::BinaryOps FlippedOpcode =
       (Opcode == Instruction::And) ? Instruction::Or : Instruction::And;
 
   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
   Value *A, *B, *C, *X, *Y;
+  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_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))
                  : BinaryOperator::CreateNot(Builder.CreateAnd(Xor, A));
     }
 
     // (~(A | B) & C) | (~(B | C) & A) --> (A ^ C) & ~B
     // (~(A & B) | C) & (~(B & C) | A) --> ~((A ^ C) & B)

llvm/test/Transforms/InstCombine/and-xor-or.ll

;
   %and2 = and i32 %not2, %b
   %or3 = or i32 %and1, %and2
   call void @use(i32 %not1)
   ret i32 %or3
 }
 
 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]]
 ;
   %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)
   ret i32 %or3
 }
 
 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]]
 ;
   %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
;
   %or2 = or i32 %a, %c
   %not2 = xor i32 %or2, -1
   %and2 = and i32 %not2, %b
   %or3 = or i32 %and1, %and2
   call void @use(i32 %or2)
   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:%.*]]
 ; CHECK-NEXT:    [[NOT1:%.*]] = xor i32 [[OR1]], -1
 ; CHECK-NEXT:    [[AND1:%.*]] = and i32 [[NOT1]], [[C:%.*]]
 ; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[A]], [[D:%.*]]
 ; CHECK-NEXT:    [[NOT2:%.*]] = xor i32 [[OR2]], -1
 ; CHECK-NEXT:    [[AND2:%.*]] = and i32 [[NOT2]], [[B]]
;
   %or2 = or i32 %not2, %b
   %and3 = and i32 %or1, %or2
   call void @use(i32 %not1)
   ret i32 %and3
 }
 
 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]]
 ;
   %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 %or1)
   ret i32 %and3
 }
 
 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]]
 ;
   %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