Index: lib/Transforms/InstCombine/InstCombineAddSub.cpp
===================================================================
--- lib/Transforms/InstCombine/InstCombineAddSub.cpp
+++ lib/Transforms/InstCombine/InstCombineAddSub.cpp
@@ -916,6 +916,65 @@
   return false;
 }
 
+// Checks if any operand is negative and we can convert add to sub.
+// This function checks for following patterns
+//   ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
+//   ADD(XOR(AND(Z, ~C), ~C), 1)    == NEG(OR(Z, C)) if C is even
+//   XOR(AND(Z, ~C), (~C + 1))      == NEG(OR(Z, C)) if C is odd
+Value *checkForNegativeOperand(BinaryOperator &I,
+                               InstCombiner::BuilderTy *Builder) {
+  Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
+
+  bool IHasNSW = I.hasNoSignedWrap();
+  bool IHasNUW = I.hasNoUnsignedWrap();
+
+  Value *X = nullptr, *Y = nullptr, *Z = nullptr;
+  const APInt *C1 = nullptr, *C2 = nullptr;
+
+  // if ONE is on other side, swap
+  if (match(RHS, m_Add(m_Value(X), m_One())))
+    std::swap(LHS, RHS);
+
+  if (match(LHS, m_Add(m_Value(X), m_One()))) {
+    // if XOR on other side, swap
+    if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
+      std::swap(X, RHS);
+
+    if (match(X, m_Xor(m_Value(Y), m_APInt(C1)))) {
+      // ADD(XOR(OR(Z, NOT(C)), C)), 1) == NEG(AND(Z, C))
+      if (match(Y, m_Or(m_Value(Z), m_APInt(C2))) && (*C1 == ~(*C2))) {
+        Value *NewAnd = Builder->CreateAnd(Z, *C1);
+        return Builder->CreateSub(RHS, NewAnd, "", IHasNUW, IHasNSW);
+      }
+      // ADD(XOR(AND(Z, ~C), ~C), 1)== NEG(OR(Z, C)) if C is even
+      else if (!C1->countTrailingZeros()) {
+        if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && (C1 == C2)) {
+          Value *NewOr = Builder->CreateOr(Z, ~(*C2));
+          return Builder->CreateSub(RHS, NewOr, "", IHasNUW, IHasNSW);
+        }
+      }
+    }
+  }
+
+  // Restore LSH and RHS
+  LHS = I.getOperand(0);
+  RHS = I.getOperand(1);
+
+  // if XOR is on other side, swap
+  if (match(RHS, m_Xor(m_Value(Y), m_APInt(C1))))
+    std::swap(LHS, RHS);
+
+  // One is absorbed in XOR
+  // XOR(AND(Z, ~C), (~C + 1)) == NEG(OR(Z, C)) if C is odd
+  if (match(LHS, m_Xor(m_Value(Y), m_APInt(C1))) && !C1->countTrailingZeros())
+    if (match(Y, m_And(m_Value(Z), m_APInt(C2))) && *C1 == (*C2 + 1)) {
+      Value *NewOr = Builder->CreateOr(Z, ~(*C2));
+      return Builder->CreateSub(RHS, NewOr, "", IHasNUW, IHasNSW);
+    }
+
+  return nullptr;
+}
+
 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
   bool Changed = SimplifyAssociativeOrCommutative(I);
   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
@@ -1025,6 +1084,8 @@
     if (Value *V = dyn_castNegVal(RHS))
       return BinaryOperator::CreateSub(LHS, V);
 
+  if (Value *V = checkForNegativeOperand(I, Builder))
+    return ReplaceInstUsesWith(I, V);
 
   {
     Constant *C2;
Index: test/Transforms/InstCombine/add2.ll
===================================================================
--- test/Transforms/InstCombine/add2.ll
+++ test/Transforms/InstCombine/add2.ll
@@ -76,3 +76,127 @@
 ; CHECK-NEXT: %add = sub <2 x i64> <i64 1, i64 2>, %A
 ; CHECK-NEXT: ret <2 x i64> %add
 }
+
+define i32 @test9(i32 %x) {
+  %x.not = or i32 %x, -1431655766
+  %neg = xor i32 %x.not, 1431655765
+  %add = add i32 %x, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test9(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, -1431655766
+; CHECK-NEXT: ret i32 [[AND]]
+}
+
+define i32 @test10(i32 %x) {
+  %x.not = and i32 %x, -1431655766
+  %add3 = xor i32 %x.not, -1431655765
+  %add1 = add nsw i32 %add3, %x
+  ret i32 %add1
+; CHECK-LABEL: @test10(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %x, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test11(i32 %x, i32 %y) {
+  %x.not = or i32 %x, -1431655766
+  %neg = xor i32 %x.not, 1431655765
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test11(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test12(i32 %x, i32 %y) {
+  %shr = ashr i32 %x, 3
+  %shr.not = or i32 %shr, -1431655766
+  %neg = xor i32 %shr.not, 1431655765
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test12(
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test13(i32 %x, i32 %y) {
+  %x.not = or i32 %x, -1431655767
+  %neg = xor i32 %x.not, 1431655766
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test13(
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 %x, 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test14(i32 %x, i32 %y) {
+  %shr = ashr i32 %x, 3
+  %shr.not = or i32 %shr, -1431655767
+  %neg = xor i32 %shr.not, 1431655766
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test14(
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[AND:%[a-z0-9]+]] = and i32 [[SHR]], 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[AND]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test15(i32 %x, i32 %y) {
+  %x.not = and i32 %x, -1431655766
+  %add2 = xor i32 %x.not, -1431655765
+  %add1 = add nsw i32 %add2, %y
+  ret i32 %add1
+; CHECK-LABEL: @test15(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test16(i32 %x, i32 %y) {
+  %shr = ashr i32 %x, 3
+  %shr.not = and i32 %shr, -1431655766
+  %add2 = xor i32 %shr.not, -1431655765
+  %add1 = add nsw i32 %add2, %y
+  ret i32 %add1
+; CHECK-LABEL: @test16(
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 [[SHR]], 1431655765
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub nsw i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test17(i32 %x, i32 %y) {
+  %x.not = and i32 %x, -1431655767
+  %neg = xor i32 %x.not, -1431655767
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test17(
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 %x, 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
+
+define i32 @test18(i32 %x, i32 %y) {
+  %shr = ashr i32 %x, 3
+  %shr.not = and i32 %shr, -1431655767
+  %neg = xor i32 %shr.not, -1431655767
+  %add = add i32 %y, 1
+  %add1 = add i32 %add, %neg
+  ret i32 %add1
+; CHECK-LABEL: @test18(
+; CHECK-NEXT: [[SHR:%[a-z0-9]+]] = ashr i32 %x, 3
+; CHECK-NEXT: [[OR:%[a-z0-9]+]] = or i32 [[SHR]], 1431655766
+; CHECK-NEXT: [[SUB:%[a-z0-9]+]] = sub i32 %y, [[OR]]
+; CHECK-NEXT: ret i32 [[SUB]]
+}
\ No newline at end of file