Index: lib/Transforms/InstCombine/InstCombineSelect.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -1635,8 +1635,7 @@
       // MAX(~a, ~b) -> ~MIN(a, b)
       // MIN(~a, ~b) -> ~MAX(a, b)
       Value *A, *B;
-      if (match(LHS, m_Not(m_Value(A))) && match(RHS, m_Not(m_Value(B))) &&
-          (LHS->getNumUses() <= 2 || RHS->getNumUses() <= 2)) {
+      if (match(LHS, m_Not(m_Value(A))) && match(RHS, m_Not(m_Value(B)))) {
         CmpInst::Predicate InvertedPred = getInverseMinMaxPred(SPF);
         Value *InvertedCmp = Builder.CreateICmp(InvertedPred, A, B);
         Value *NewSel = Builder.CreateSelect(InvertedCmp, A, B);
Index: test/Transforms/InstCombine/max-of-nots.ll
===================================================================
--- test/Transforms/InstCombine/max-of-nots.ll
+++ test/Transforms/InstCombine/max-of-nots.ll
@@ -65,8 +65,9 @@
 ; CHECK-LABEL: @umin_not_2_extra_use(
 ; CHECK-NEXT:    [[NX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[NY:%.*]] = xor i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[CMPXY:%.*]] = icmp ult i8 [[NX]], [[NY]]
-; CHECK-NEXT:    [[MINXY:%.*]] = select i1 [[CMPXY]], i8 [[NX]], i8 [[NY]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X]], [[Y]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Y]]
+; CHECK-NEXT:    [[MINXY:%.*]] = xor i8 [[TMP2]], -1
 ; CHECK-NEXT:    call void @extra_use(i8 [[NX]])
 ; CHECK-NEXT:    call void @extra_use(i8 [[NY]])
 ; CHECK-NEXT:    ret i8 [[MINXY]]
@@ -139,10 +140,11 @@
 ; CHECK-NEXT:    [[XN:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    [[YN:%.*]] = xor i8 [[Y:%.*]], -1
 ; CHECK-NEXT:    [[ZN:%.*]] = xor i8 [[Z:%.*]], -1
-; CHECK-NEXT:    [[CMPXZ:%.*]] = icmp ult i8 [[XN]], [[ZN]]
-; CHECK-NEXT:    [[MINXZ:%.*]] = select i1 [[CMPXZ]], i8 [[XN]], i8 [[ZN]]
-; CHECK-NEXT:    [[CMPXYZ:%.*]] = icmp ult i8 [[MINXZ]], [[YN]]
-; CHECK-NEXT:    [[MINXYZ:%.*]] = select i1 [[CMPXYZ]], i8 [[MINXZ]], i8 [[YN]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X]], [[Z]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Z]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i8 [[TMP2]], [[Y]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[Y]]
+; CHECK-NEXT:    [[MINXYZ:%.*]] = xor i8 [[TMP4]], -1
 ; CHECK-NEXT:    call void @use8(i8 [[XN]])
 ; CHECK-NEXT:    call void @use8(i8 [[YN]])
 ; CHECK-NEXT:    call void @use8(i8 [[ZN]])
@@ -163,16 +165,14 @@
 
 define void @umin3_not_all_ops_extra_uses_invert_subs(i8 %x, i8 %y, i8 %z) {
 ; CHECK-LABEL: @umin3_not_all_ops_extra_uses_invert_subs(
-; CHECK-NEXT:    [[XN:%.*]] = xor i8 [[X:%.*]], -1
-; CHECK-NEXT:    [[YN:%.*]] = xor i8 [[Y:%.*]], -1
-; CHECK-NEXT:    [[ZN:%.*]] = xor i8 [[Z:%.*]], -1
-; CHECK-NEXT:    [[CMPXZ:%.*]] = icmp ult i8 [[XN]], [[ZN]]
-; CHECK-NEXT:    [[MINXZ:%.*]] = select i1 [[CMPXZ]], i8 [[XN]], i8 [[ZN]]
-; CHECK-NEXT:    [[CMPXYZ:%.*]] = icmp ult i8 [[MINXZ]], [[YN]]
-; CHECK-NEXT:    [[MINXYZ:%.*]] = select i1 [[CMPXYZ]], i8 [[MINXZ]], i8 [[YN]]
-; CHECK-NEXT:    [[XMIN:%.*]] = sub i8 [[XN]], [[MINXYZ]]
-; CHECK-NEXT:    [[YMIN:%.*]] = sub i8 [[YN]], [[MINXYZ]]
-; CHECK-NEXT:    [[ZMIN:%.*]] = sub i8 [[ZN]], [[MINXYZ]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i8 [[X:%.*]], [[Z:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i8 [[X]], i8 [[Z]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp ugt i8 [[TMP2]], [[Y:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = select i1 [[TMP3]], i8 [[TMP2]], i8 [[Y]]
+; CHECK-NEXT:    [[MINXYZ:%.*]] = xor i8 [[TMP4]], -1
+; CHECK-NEXT:    [[XMIN:%.*]] = sub i8 [[TMP4]], [[X]]
+; CHECK-NEXT:    [[YMIN:%.*]] = sub i8 [[TMP4]], [[Y]]
+; CHECK-NEXT:    [[ZMIN:%.*]] = sub i8 [[TMP4]], [[Z]]
 ; CHECK-NEXT:    call void @use8(i8 [[MINXYZ]])
 ; CHECK-NEXT:    call void @use8(i8 [[XMIN]])
 ; CHECK-NEXT:    call void @use8(i8 [[YMIN]])