Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1768,6 +1768,31 @@
     return SelectInst::Create(Cmp, Neg, A);
   }
 
+  // Fold (neg (min/max ~X, C)) -> (add (min/max X, ~C), 1)
+  if (match(Op0, m_ZeroInt()) && Op1->hasOneUse()) {
+    Value *LHS, *RHS;
+    SelectPatternFlavor SPF = matchSelectPattern(Op1, LHS, RHS).Flavor;
+    if (SelectPatternResult::isMinOrMax(SPF)) {
+      Value *X;
+      if (match(LHS, m_Not(m_Value(X))) &&
+          IsFreeToInvert(RHS, RHS->hasOneUse())) {
+        Value *NotY = Builder.CreateNot(RHS);
+        Value *MinMax = Builder.CreateSelect(
+            Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
+        Value *One = ConstantInt::get(MinMax->getType(), 1);
+        return BinaryOperator::CreateAdd(MinMax, One);
+      }
+      if (match(RHS, m_Not(m_Value(X))) &&
+          IsFreeToInvert(LHS, LHS->hasOneUse())) {
+        Value *NotY = Builder.CreateNot(RHS);
+        Value *MinMax = Builder.CreateSelect(
+            Builder.CreateICmp(getInverseMinMaxPred(SPF), X, NotY), X, NotY);
+        Value *One = ConstantInt::get(MinMax->getType(), 1);
+        return BinaryOperator::CreateAdd(MinMax, One);
+      }
+    }
+  }
+
   bool Changed = false;
   if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {
     Changed = true;
Index: test/Transforms/InstCombine/sub.ll
===================================================================
--- test/Transforms/InstCombine/sub.ll
+++ test/Transforms/InstCombine/sub.ll
@@ -1056,3 +1056,93 @@
   %D = sub <2 x i32> <i32 2, i32 2>, %C
   ret <2 x i32> %D
 }
+
+; Tests for (neg (max ~X, C)) -> ((min X, ~C) + 1). Same for min.
+define i32 @test64(i32 %x) {
+; CHECK-LABEL: @test64(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt i32 [[X:%.*]], 255
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 255
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %1 = xor i32 %x, -1
+  %2 = icmp sgt i32 %1, -256
+  %3 = select i1 %2, i32 %1, i32 -256
+  %res = sub i32 0, %3
+  ret i32 %res
+}
+
+define i32 @test65(i32 %x) {
+; CHECK-LABEL: @test65(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp sgt i32 [[X:%.*]], -256
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 -256
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %1 = xor i32 %x, -1
+  %2 = icmp slt i32 %1, 255
+  %3 = select i1 %2, i32 %1, i32 255
+  %res = sub i32 0, %3
+  ret i32 %res
+}
+
+define i32 @test66(i32 %x) {
+; CHECK-LABEL: @test66(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[X:%.*]], -101
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 -101
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %1 = xor i32 %x, -1
+  %2 = icmp ugt i32 %1, 100
+  %3 = select i1 %2, i32 %1, i32 100
+  %res = sub i32 0, %3
+  ret i32 %res
+}
+
+define i32 @test67(i32 %x) {
+; CHECK-LABEL: @test67(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i32 [[X:%.*]], 100
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i32 [[X]], i32 100
+; CHECK-NEXT:    [[RES:%.*]] = add i32 [[TMP2]], 1
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %1 = xor i32 %x, -1
+  %2 = icmp ult i32 %1, -101
+  %3 = select i1 %2, i32 %1, i32 -101
+  %res = sub i32 0, %3
+  ret i32 %res
+}
+
+; Check splat vectors too
+define <2 x i32> @test68(<2 x i32> %x) {
+; CHECK-LABEL: @test68(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp slt <2 x i32> [[X:%.*]], <i32 255, i32 255>
+; CHECK-NEXT:    [[TMP2:%.*]] = select <2 x i1> [[TMP1]], <2 x i32> [[X]], <2 x i32> <i32 255, i32 255>
+; CHECK-NEXT:    [[RES:%.*]] = add <2 x i32> [[TMP2]], <i32 1, i32 1>
+; CHECK-NEXT:    ret <2 x i32> [[RES]]
+;
+  %1 = xor <2 x i32> %x, <i32 -1, i32 -1>
+  %2 = icmp sgt <2 x i32> %1, <i32 -256, i32 -256>
+  %3 = select <2 x i1> %2, <2 x i32> %1, <2 x i32> <i32 -256, i32 -256>
+  %res = sub <2 x i32> zeroinitializer, %3
+  ret <2 x i32> %res
+}
+
+; Don't transform if the select has an additional use.
+define i32 @test69(i32 %x, i32* %y) {
+; CHECK-LABEL: @test69(
+; CHECK-NEXT:    [[TMP1:%.*]] = xor i32 [[X:%.*]], -1
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp sgt i32 [[TMP1]], -256
+; CHECK-NEXT:    [[TMP3:%.*]] = select i1 [[TMP2]], i32 [[TMP1]], i32 -256
+; CHECK-NEXT:    [[RES:%.*]] = sub i32 0, [[TMP3]]
+; CHECK-NEXT:    store i32 [[TMP3]], i32* [[Y:%.*]], align 4
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+  %1 = xor i32 %x, -1
+  %2 = icmp sgt i32 %1, -256
+  %3 = select i1 %2, i32 %1, i32 -256
+  %res = sub i32 0, %3
+  store i32 %3, i32* %y
+  ret i32 %res
+}