Index: lib/Transforms/InstCombine/InstCombineSelect.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -1145,12 +1145,14 @@
     if (Instruction *FoldI = FoldSelectIntoOp(SI, TrueVal, FalseVal))
       return FoldI;
 
+    Value *LHS, *RHS, *LHS2, *RHS2;
+    SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS);
+
     // MAX(MAX(a, b), a) -> MAX(a, b)
     // MIN(MIN(a, b), a) -> MIN(a, b)
     // MAX(MIN(a, b), a) -> a
     // MIN(MAX(a, b), a) -> a
-    Value *LHS, *RHS, *LHS2, *RHS2;
-    if (SelectPatternFlavor SPF = MatchSelectPattern(&SI, LHS, RHS)) {
+    if (SPF) {
       if (SelectPatternFlavor SPF2 = MatchSelectPattern(LHS, LHS2, RHS2))
         if (Instruction *R = FoldSPFofSPF(cast<Instruction>(LHS),SPF2,LHS2,RHS2,
                                           SI, SPF, RHS))
@@ -1161,6 +1163,53 @@
           return R;
     }
 
+    // MAX(~a, ~b) -> ~MIN(a, b)
+    if (SPF == SPF_SMAX || SPF == SPF_UMAX) {
+
+      // Is it free to change the ICmpInst and the SelectInst using V to use ~V
+      // instead?
+      auto IsFreeToInvert = [](Value *V) {
+        if (match(V, m_Not(m_Value())))
+          return true;
+
+        // If the `V` is of the form `A + Constant` then `-1 - V` can be folded
+        // into `(-1 - Constant) -A`.
+        //
+        // TODO: we can be smarter on the hasNUses(2) part if needed.
+        BinaryOperator *BO = dyn_cast<BinaryOperator>(V);
+        if (BO && V->hasNUses(2))
+          if (BO->getOpcode() == Instruction::Add ||
+              BO->getOpcode() == Instruction::Sub)
+            return isa<Constant>(BO->getOperand(0)) ||
+              isa<Constant>(BO->getOperand(1));
+
+        return false;
+      };
+
+      if (IsFreeToInvert(LHS) && IsFreeToInvert(RHS)) {
+        // Even when using `a` instead of `~a` and `b` instead of `~b` is free,
+        // the transform itself is a pessimization unless the extra bitwise not
+        // on the select can be justified.  TODO: we can be smarter here,
+        // especially in recognizing chains of smin / umin operations.
+
+        bool Profitable =
+          (LHS->hasNUses(2) && match(LHS, m_Not(m_Value()))) ||
+          (RHS->hasNUses(2) && match(RHS, m_Not(m_Value()))) ||
+          (SI.hasOneUse() && match(*SI.user_begin(), m_Not(m_Value())));
+
+        if (Profitable) {
+          Value *NewLHS = Builder->CreateNot(LHS);
+          Value *NewRHS = Builder->CreateNot(RHS);
+          Value *NewCmp = SPF == SPF_SMAX ?
+            Builder->CreateICmpSLT(NewLHS, NewRHS) :
+            Builder->CreateICmpULT(NewLHS, NewRHS);
+          Value *NewSI = Builder->CreateNot(
+            Builder->CreateSelect(NewCmp, NewLHS, NewRHS));
+          return ReplaceInstUsesWith(SI, NewSI);
+        }
+      }
+    }
+
     // TODO.
     // ABS(-X) -> ABS(X)
   }
Index: test/Transforms/InstCombine/max-of-nots.ll
===================================================================
--- /dev/null
+++ test/Transforms/InstCombine/max-of-nots.ll
@@ -0,0 +1,68 @@
+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+define i32 @compute_min_2(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_2
+ entry:
+  %not_x = sub i32 -1, %x
+  %not_y = sub i32 -1, %y
+  %cmp = icmp sgt i32 %not_x, %not_y
+  %not_min = select i1 %cmp, i32 %not_x, i32 %not_y
+  %min = sub i32 -1, %not_min
+  ret i32 %min
+
+; CHECK: %0 = icmp slt i32 %x, %y
+; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y
+; CHECK-NEXT: ret i32 %1
+}
+
+define i32 @compute_min_3(i32 %x, i32 %y, i32 %z) {
+; CHECK-LABEL: compute_min_3
+ entry:
+  %not_x = sub i32 -1, %x
+  %not_y = sub i32 -1, %y
+  %not_z = sub i32 -1, %z
+  %cmp_1 = icmp sgt i32 %not_x, %not_y
+  %not_min_1 = select i1 %cmp_1, i32 %not_x, i32 %not_y
+  %cmp_2 = icmp sgt i32 %not_min_1, %not_z
+  %not_min_2 = select i1 %cmp_2, i32 %not_min_1, i32 %not_z
+  %min = sub i32 -1, %not_min_2
+  ret i32 %min
+
+; CHECK: %0 = icmp slt i32 %x, %y
+; CHECK-NEXT: %1 = select i1 %0, i32 %x, i32 %y
+; CHECK-NEXT: %2 = icmp slt i32 %1, %z
+; CHECK-NEXT: %3 = select i1 %2, i32 %1, i32 %z
+; CHECK-NEXT: ret i32 %3
+}
+
+define i32 @compute_min_arithmetic(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_arithmetic
+ entry:
+  %not_value = sub i32 3, %x
+  %not_y = sub i32 -1, %y
+  %cmp = icmp sgt i32 %not_value, %not_y
+  %not_min = select i1 %cmp, i32 %not_value, i32 %not_y
+  ret i32 %not_min
+
+; CHECK: %0 = add i32 %x, -4
+; CHECK-NEXT: %1 = icmp slt i32 %0, %y
+; CHECK-NEXT: %2 = select i1 %1, i32 %0, i32 %y
+; CHECK-NEXT: %3 = xor i32 %2, -1
+; CHECK-NEXT: ret i32 %3
+}
+
+declare void @fake_use(i32)
+
+define i32 @compute_min_pessimization(i32 %x, i32 %y) {
+; CHECK-LABEL: compute_min_pessimization
+ entry:
+  %not_value = sub i32 3, %x
+  call void @fake_use(i32 %not_value)
+  %not_y = sub i32 -1, %y
+  %cmp = icmp sgt i32 %not_value, %not_y
+; CHECK: %not_value = sub i32 3, %x
+; CHECK: %cmp = icmp sgt i32 %not_value, %not_y
+  %not_min = select i1 %cmp, i32 %not_value, i32 %not_y
+  %min = sub i32 -1, %not_min
+  ret i32 %min
+}