Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -1191,6 +1191,26 @@
     }
   }
 
+  // A + ~Select(P, A, B) -> Select(P, -1, A+~B) If B is freely invertible
+  // A + ~Select(P, B, A) -> Select(P, A+~B, -1)
+  // We require B to be freely invertible as this may break apart the
+  // representation of min/max's. If B is freely invertable, we know we
+  // are at least lowering the number of IR instructions.
+  Value *Select, *Pred;
+  auto SelectPred = m_CombineAnd(
+      m_CombineOr(m_Select(m_Value(Pred), m_Deferred(A), m_Value(B)),
+                  m_Select(m_Value(Pred), m_Value(B), m_Deferred(A))),
+      m_Value(Select));
+  if (match(&I, m_c_BinOp(m_Value(A), m_OneUse(m_Not(m_OneUse(SelectPred))))) &&
+      IsFreeToInvert(B, B->hasOneUse())) {
+    Value *NotB = Builder.CreateNot(B);
+    Value *TrueVal = Builder.CreateAdd(A, NotB);
+    Value *FalseVal = ConstantInt::getAllOnesValue(A->getType());
+    if (cast<SelectInst>(Select)->getTrueValue() == A)
+      std::swap(TrueVal, FalseVal);
+    return SelectInst::Create(Pred, TrueVal, FalseVal);
+  }
+
   if (Instruction *Ext = narrowMathIfNoOverflow(I))
     return Ext;
 
Index: test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
===================================================================
--- test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
+++ test/Transforms/IndVarSimplify/replace-loop-exit-folds.ll
@@ -7,14 +7,8 @@
 define i32 @remove_loop(i32 %size) {
 ; CHECK-LABEL: @remove_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SIZE:%.*]], 31
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[SIZE]], i32 31
-; CHECK-NEXT:    [[UMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[SIZE]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -32
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[SIZE]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[SIZE:%.*]], 31
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %while.cond
@@ -33,22 +27,16 @@
 define i32 @used_loop(i32 %size) minsize {
 ; CHECK-LABEL: @used_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[SIZE:%.*]], 31
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[SIZE]], i32 31
-; CHECK-NEXT:    [[UMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[SIZE]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -32
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[SIZE_ADDR_0:%.*]] = phi i32 [ [[SIZE]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_COND]] ]
+; CHECK-NEXT:    [[SIZE_ADDR_0:%.*]] = phi i32 [ [[SIZE:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_COND]] ]
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[SIZE_ADDR_0]], 31
 ; CHECK-NEXT:    [[SUB]] = add i32 [[SIZE_ADDR_0]], -32
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_COND]], label [[WHILE_END:%.*]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[SIZE]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[SIZE]], 31
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %while.cond
@@ -69,12 +57,9 @@
 define i32 @test_signed_while(i32 %S) {
 ; CHECK-LABEL: @test_signed_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp slt i32 [[S:%.*]], 31
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp sgt i32 [[S:%.*]], 31
 ; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[S]], i32 31
-; CHECK-NEXT:    [[SMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[SMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 32
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -32
+; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], 2147483616
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
@@ -85,8 +70,8 @@
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[S]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i32 [[S]], [[TMP2]]
+; CHECK-NEXT:    ret i32 [[TMP3]]
 ;
 entry:
   br label %while.cond
@@ -144,15 +129,9 @@
 define i32 @test_unsigned_while(i32 %S) {
 ; CHECK-LABEL: @test_unsigned_while(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[S:%.*]], 15
-; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i32 [[S]], i32 15
-; CHECK-NEXT:    [[UMAX:%.*]] = xor i32 [[TMP1]], -1
-; CHECK-NEXT:    [[TMP2:%.*]] = add i32 [[UMAX]], [[S]]
-; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 16
-; CHECK-NEXT:    [[TMP4:%.*]] = and i32 [[TMP3]], -16
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
-; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
+; CHECK-NEXT:    [[S_ADDR_0:%.*]] = phi i32 [ [[S:%.*]], [[ENTRY:%.*]] ], [ [[SUB:%.*]], [[WHILE_BODY:%.*]] ]
 ; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i32 [[S_ADDR_0]], 15
 ; CHECK-NEXT:    br i1 [[CMP]], label [[WHILE_BODY]], label [[WHILE_END:%.*]]
 ; CHECK:       while.body:
@@ -160,8 +139,8 @@
 ; CHECK-NEXT:    tail call void @call()
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
-; CHECK-NEXT:    [[TMP5:%.*]] = sub i32 [[S]], [[TMP4]]
-; CHECK-NEXT:    ret i32 [[TMP5]]
+; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[S]], 15
+; CHECK-NEXT:    ret i32 [[TMP0]]
 ;
 entry:
   br label %while.cond
Index: test/Transforms/InstCombine/add-select.ll
===================================================================
--- test/Transforms/InstCombine/add-select.ll
+++ test/Transforms/InstCombine/add-select.ll
@@ -34,9 +34,8 @@
 define i32 @A_plus_not_smin_invertible(i32 %A) {
 ; CHECK-LABEL: @A_plus_not_smin_invertible(
 ; CHECK-NEXT:    [[L0:%.*]] = icmp slt i32 [[A:%.*]], 31
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L0]], i32 [[A]], i32 31
-; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[L1]], -1
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[NOT]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[A]], -32
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[L0]], i32 -1, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp slt i32 %A, 31
@@ -49,9 +48,8 @@
 define i32 @A_plus_not_smin_swapped(i32 %A) {
 ; CHECK-LABEL: @A_plus_not_smin_swapped(
 ; CHECK-NEXT:    [[L0:%.*]] = icmp slt i32 [[A:%.*]], 31
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L0]], i32 [[A]], i32 31
-; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[L1]], -1
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[NOT]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[A]], -32
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[L0]], i32 -1, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp slt i32 %A, 31
@@ -64,9 +62,8 @@
 define i32 @A_plus_not_smax_invertible(i32 %A) {
 ; CHECK-LABEL: @A_plus_not_smax_invertible(
 ; CHECK-NEXT:    [[L0:%.*]] = icmp sgt i32 [[A:%.*]], 31
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[L0]], i32 [[A]], i32 31
-; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[L1]], -1
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[NOT]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[A]], -32
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[L0]], i32 -1, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %l0 = icmp sgt i32 %A, 31
@@ -78,10 +75,8 @@
 
 define i32 @usebase(i1 %p, i32 %A, i32 %Bi) {
 ; CHECK-LABEL: @usebase(
-; CHECK-NEXT:    [[B:%.*]] = xor i32 [[BI:%.*]], -1
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[P:%.*]], i32 [[A:%.*]], i32 [[B]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[L1]], -1
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[NOT]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[BI:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[P:%.*]], i32 -1, i32 [[TMP1]]
 ; CHECK-NEXT:    ret i32 [[X]]
 ;
   %B = xor i32 %Bi, -1
@@ -94,9 +89,8 @@
 define i32 @useB(i1 %p, i32 %A, i32 %Bi) {
 ; CHECK-LABEL: @useB(
 ; CHECK-NEXT:    [[B:%.*]] = xor i32 [[BI:%.*]], -1
-; CHECK-NEXT:    [[L1:%.*]] = select i1 [[P:%.*]], i32 [[A:%.*]], i32 [[B]]
-; CHECK-NEXT:    [[NOT:%.*]] = xor i32 [[L1]], -1
-; CHECK-NEXT:    [[X:%.*]] = add i32 [[NOT]], [[A]]
+; CHECK-NEXT:    [[TMP1:%.*]] = add i32 [[BI]], [[A:%.*]]
+; CHECK-NEXT:    [[X:%.*]] = select i1 [[P:%.*]], i32 -1, i32 [[TMP1]]
 ; CHECK-NEXT:    call void @use(i32 [[B]])
 ; CHECK-NEXT:    ret i32 [[X]]
 ;