diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
--- a/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
@@ -1082,13 +1082,12 @@
     // Examples:
     // max ~A, ~Y --> ~(min A, Y)
     // max ~A, C --> ~(min A, ~C)
+    // max ~A, (max ~Y, ~Z) --> ~min( A, (min Y, Z))
     auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * {
       Value *A;
       if (match(X, m_OneUse(m_Not(m_Value(A)))) &&
           !isFreeToInvert(A, A->hasOneUse()) &&
-          // Passing false to only consider m_Not and constants.
-          // TODO: Allow Y to match other patterns by checking use count.
-          isFreeToInvert(Y, false)) {
+          isFreeToInvert(Y, Y->hasOneUse())) {
         Value *NotY = Builder.CreateNot(Y);
         Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
         Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, A, NotY);
diff --git a/llvm/test/Transforms/InstCombine/minmax-intrinsics.ll b/llvm/test/Transforms/InstCombine/minmax-intrinsics.ll
--- a/llvm/test/Transforms/InstCombine/minmax-intrinsics.ll
+++ b/llvm/test/Transforms/InstCombine/minmax-intrinsics.ll
@@ -508,13 +508,13 @@
 
 define i8 @umin_of_not_and_smax(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @umin_of_not_and_smax(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTY]])
 ; CHECK-NEXT:    [[NOTZ:%.*]] = xor i8 [[Z:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTZ]])
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.smax.i8(i8 [[NOTY]], i8 [[NOTZ]])
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.umin.i8(i8 [[M1]], i8 [[NOTX]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.smin.i8(i8 [[Y]], i8 [[Z]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.umax.i8(i8 [[X:%.*]], i8 [[TMP1]])
+; CHECK-NEXT:    [[M2:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %notx = xor i8 %x, -1
@@ -529,13 +529,13 @@
 
 define i8 @smin_of_umax_and_not(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @smin_of_umax_and_not(
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NOTY:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTY]])
 ; CHECK-NEXT:    [[NOTZ:%.*]] = xor i8 [[Z:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTZ]])
-; CHECK-NEXT:    [[M1:%.*]] = call i8 @llvm.umax.i8(i8 [[NOTY]], i8 [[NOTZ]])
-; CHECK-NEXT:    [[M2:%.*]] = call i8 @llvm.smin.i8(i8 [[NOTX]], i8 [[M1]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y]], i8 [[Z]])
+; CHECK-NEXT:    [[TMP2:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 [[TMP1]])
+; CHECK-NEXT:    [[M2:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    ret i8 [[M2]]
 ;
   %notx = xor i8 %x, -1