[InstCombine] (A + 1) + (B ^ -1) --> A - B

[gilr]

Summary

Turn canonicalized subtraction back into (-1 - B) and combine it with (A + 1) into (A - B).
This is similar to the folding already done for (B ^ -1) + Const into (-1 + Const) - B.

[lebedev.ri]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1217

The constants are already canonicalized to RHS, so it's just m_Add().

[gilr]

Impl. Roman's comment - m_Add instead of m_c_Add.

[spatel]

LGTM - see inline for some test suggestions.

test/Transforms/InstCombine/add.ll

801–802

1. Commuting the constants in "%C" and "%D" distracts from the meaningful commute of "%E", so don't do that.
2. It would provide more coverage if one of the tests used vector types (or add a dedicated test for vectors).
3. It's a matter of taste, but I prefer to have the code comment above the function rather than embedded in the code.
4. Similarly, give the test a meaningful name: "@add_not_increment"?
5. Always prefer to commit the tests with baseline CHECKs as a preliminary step to the patched tests.

[gilr]

Impl. Sanjay comments.
Thanks for taking the time guys!

lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 
   // A + -B  -->  A - B
   if (match(RHS, m_Neg(m_Value(B))))
     return BinaryOperator::CreateSub(LHS, B);
 
   if (Value *V = checkForNegativeOperand(I, Builder))
     return replaceInstUsesWith(I, V);
 
+  // (A + 1) + ~B --> A - B
+  // ~B + (A + 1) --> A - B
+  if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))))
+    return BinaryOperator::CreateSub(A, B);
+
   // X % C0 + (( X / C0 ) % C1) * C0 => X % (C0 * C1)
   if (Value *V = SimplifyAddWithRemainder(I)) return replaceInstUsesWith(I, V);
 
   // A+B --> A|B iff A and B have no bits set in common.
   if (haveNoCommonBitsSet(LHS, RHS, DL, &AC, &I, &DT))
     return BinaryOperator::CreateOr(LHS, RHS);
 
   // FIXME: We already did a check for ConstantInt RHS above this.

test/Transforms/InstCombine/add.ll

 delay:
   br label %final
 
 final:
   %A = phi <2 x i32> [ <i32 1000, i32 2500>, %entry ], [ <i32 10, i32 30>, %delay ]
   %value = add <2 x i32> <i32 123, i32 333>, %A
   ret <2 x i32> %value
 }
+
+; E = (A + 1) + ~B = A - B
+define i32 @add_not_increment(i32 %A, i32 %B) {
+; CHECK-LABEL: @add_not_increment(
+; CHECK-NEXT:    [[E:%.*]] = sub i32 %A, %B
+; CHECK-NEXT:    ret i32 [[E]]
+;
+  %C = xor i32 %B, -1
+  %D = add i32 %A, 1
+  %E = add i32 %D, %C
+  ret i32 %E
+}
+
+; E = (A + 1) + ~B = A - B
+define <2 x i32> @add_not_increment_vec(<2 x i32> %A, <2 x i32> %B) {
+; CHECK-LABEL: @add_not_increment_vec(
+; CHECK-NEXT:    [[E:%.*]] = sub <2 x i32> %A, %B
+; CHECK-NEXT:    ret <2 x i32> [[E]]
+;
+  %C = xor <2 x i32> %B, <i32 -1, i32 -1>
+  %D = add <2 x i32> %A, <i32 1, i32 1>
+  %E = add <2 x i32> %D, %C
+  ret <2 x i32> %E
+}
+
+; E = ~B + (1 + A) = A - B
+define i32 @add_not_increment_commuted(i32 %A, i32 %B) {
+; CHECK-LABEL: @add_not_increment_commuted(
+; CHECK-NEXT:    [[E:%.*]] = sub i32 %A, %B
+; CHECK-NEXT:    ret i32 [[E]]
+;
+  %C = xor i32 %B, -1
+  %D = add i32 %A, 1
+  %E = add i32 %C, %D
+  ret i32 %E
+}
+