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
@@ -1076,21 +1076,31 @@
       }
     }
 
-    if (match(I0, m_Not(m_Value(X)))) {
-      // max (not X), (not Y) --> not (min X, Y)
-      Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
-      if (match(I1, m_Not(m_Value(Y))) &&
-          (I0->hasOneUse() || I1->hasOneUse())) {
-        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, Y);
-        return BinaryOperator::CreateNot(InvMaxMin);
-      }
-      // max (not X), C --> not(min X, ~C)
-      if (match(I1, m_Constant(C)) && I0->hasOneUse()) {
-        Constant *NotC = ConstantExpr::getNot(C);
-        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, X, NotC);
+    // If we can eliminate ~A and Y is free to invert:
+    // max ~A, Y --> ~(min A, ~Y)
+    //
+    // Examples:
+    // max ~A, ~Y --> ~(min A, Y)
+    // max ~A, C --> ~(min A, ~C)
+    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)) {
+        Value *NotY = Builder.CreateNot(Y);
+        Intrinsic::ID InvID = getInverseMinMaxIntrinsic(IID);
+        Value *InvMaxMin = Builder.CreateBinaryIntrinsic(InvID, A, NotY);
         return BinaryOperator::CreateNot(InvMaxMin);
       }
-    }
+      return nullptr;
+    };
+
+    if (Instruction *I = moveNotAfterMinMax(I0, I1))
+      return I;
+    if (Instruction *I = moveNotAfterMinMax(I1, I0))
+      return I;
 
     // smax(X, -X) --> abs(X)
     // smin(X, -X) --> -abs(X)
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
@@ -411,7 +411,7 @@
 ; CHECK-LABEL: @umax_of_nots(
 ; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    call void @use(i8 [[NOTX]])
-; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[X]], i8 [[Y:%.*]])
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.umin.i8(i8 [[Y:%.*]], i8 [[X]])
 ; CHECK-NEXT:    [[M:%.*]] = xor i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
@@ -548,6 +548,19 @@
   ret i8 %m2
 }
 
+; Negative test - don't infinite loop on constant expression
+
+define i8 @umin_of_not_and_nontrivial_const(i8 %x) {
+; CHECK-LABEL: @umin_of_not_and_nontrivial_const(
+; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
+; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[NOTX]], i8 ptrtoint (i8 (i8)* @umin_of_not_and_nontrivial_const to i8))
+; CHECK-NEXT:    ret i8 [[M]]
+;
+  %notx = xor i8 %x, -1
+  %m = call i8 @llvm.umin.i8(i8 ptrtoint (i8(i8)* @umin_of_not_and_nontrivial_const to i8), i8 %notx)
+  ret i8 %m
+}
+
 ; Negative test - too many uses
 
 define i8 @umin_of_not_and_const_uses(i8 %x) {