[InstCombine] fold add(add(A, ~B), 1) -> sub(A, B)

[deadalnix]

Summary

As per title.

[RKSimon]

vector test?

[RKSimon]

Test for ((A + 1) + ~B) and ((~B + 1) + A) cases?

[spatel]

test/Transforms/InstCombine/add.ll

955

This is not testing what you expected. The operands are getting commuted independently of this patch, so it's effectively the same test as the next one. Grep for "thwart" in the instcombine regression test dir to see some options to work around that.

[spatel]

In D58877#1416363, @RKSimon wrote:

Test for ((A + 1) + ~B) and ((~B + 1) + A) cases?

We already get that case in instcombine. So this brings up a question of division-of-labor. The -reassociate pass will take the pattern from this patch and form the above because it "ranks" the constant 1 above a variable operand. Then instcombine can fold it. Is that good enough, or do we need to handle a pattern that is not canonical based on the output of -reassociate. Unless we have evidence that this is slipping through a normal opt -O1 pipeline, we probably do not need this patch?

[deadalnix]

Add extra ops to ensure proper ordering.

Interestingly, IntCombine chose to flip the sign of the constant of the mul and go with an add insteadof a sub, which is also perfectly fine.

[deadalnix]

In D58877#1416363, @RKSimon wrote:

Test for ((A + 1) + ~B) and ((~B + 1) + A) cases?

The first is already handled explicitly. The second is handled via ((~B + 1) + A) -> ((0-B) + A) -> A - B . There are tests for both patterns already.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1177

See here.

[deadalnix]

Ping ?

[spatel]

The logic/tests look ok, but the question of necessity/usefulness has not been answered. Is there evidence that this pattern will ever reach instcombine in a normal optimization pipeline that includes -reassociate?

[deadalnix]

@spatel I'm not sure, you tell me :) The history of this patch is that this pattern shows up in practice post legalization, so I submitted a patch for it for DAGCombiner. From there, @ lebedev.ri noticed that InstCombine wasn't doing it and suggested it to be added there as well.

As far as I can tell, -reassociate also fails to trigger this transform: https://godbolt.org/z/gweK6j

[spatel]

In D58877#1426695, @deadalnix wrote:

@spatel I'm not sure, you tell me :) The history of this patch is that this pattern shows up in practice post legalization, so I submitted a patch for it for DAGCombiner. From there, @ lebedev.ri noticed that InstCombine wasn't doing it and suggested it to be added there as well.

As far as I can tell, -reassociate also fails to trigger this transform: https://godbolt.org/z/gweK6j

You have to run reassociate before instcombine to get the expected ranking of operands:
https://godbolt.org/z/5XHhTh

So I agree that we needed the backend patch, but I don't see any evidence that this is needed within instcombine yet. The difference is that - in the backend - DAGCombiner is doing the job of both of the IR passes (reassociate is a canonicalization pass that works with instcombine). If we don't see this pattern after a normal IR optimization sequence, then I don't think we want to add it to instcombine (it would likely infinitesimally increase compile-time with no potential benefit). One way to see if there's any benefit to this patch would be to add a transform statistic, build the test-suite or some other substantial codebase, and see if this transform ever fires.

[deadalnix]

Is someone of a different opinion than @spatel ? If not, I'll abandon this patch soon.

[lebedev.ri]

In D58877#1439691, @deadalnix wrote:

Is someone of a different opinion than @spatel ? If not, I'll abandon this patch soon.

I haven't tried this on a whole llvm stage-2 build, but on small-ish codebase i have tried this does not seem to be reachable.
(You could, of course, try stage-2 build, that will have more coverage.)
Sorry for lost effort, i should have seen that -reassociate would have solved this :(

[deadalnix]

Ok, abandoning it as it doesn't seems to be necessary.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombiner::foldAddWithConstant(BinaryOperator &Add) {
   // ~X + C --> (C-1) - X
   if (match(Op0, m_Not(m_Value(X))))
     return BinaryOperator::CreateSub(SubOne(Op1C), X);
 
   const APInt *C;
   if (!match(Op1, m_APInt(C)))
     return nullptr;
 
+  // (X + ~Y) + 1 --> X - Y
+  if (C->isOneValue() && match(Op0, m_c_Add(m_Value(X), m_Not(m_Value(Y)))))
+    return BinaryOperator::CreateSub(X, Y);
+
   if (C->isSignMask()) {
     // If wrapping is not allowed, then the addition must set the sign bit:
     // X + (signmask) --> X | signmask
     if (Add.hasNoSignedWrap() || Add.hasNoUnsignedWrap())
       return BinaryOperator::CreateOr(Op0, Op1);
 
     // If wrapping is allowed, then the addition flips the sign bit of LHS:
     // X + (signmask) --> X ^ signmask
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);
 

test/Transforms/InstCombine/add.ll

;
   %E = add i32 %C, %D
   ret i32 %E
 }
 
 ; E = (A + ~B) + 1 = A - B
 define i32 @add_to_sub(i32 %M, i32 %B) {
 ; CHECK-LABEL: @add_to_sub(
 ; CHECK-NEXT:    [[A:%.*]] = mul i32 [[M:%.*]], 42
-; CHECK-NEXT:    [[C:%.*]] = xor i32 [[B:%.*]], -1
-; CHECK-NEXT:    [[D:%.*]] = add i32 [[A]], [[C]]
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[D]], 1
+; CHECK-NEXT:    [[E:%.*]] = sub i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %A = mul i32 %M, 42          ; thwart complexity-based ordering
   %C = xor i32 %B, -1
   %D = add i32 %A, %C
   %E = add i32 %D, 1
   ret i32 %E
 }
 
 ; E = (~B + A) + 1 = A - B
 define i32 @add_to_sub2(i32 %A, i32 %M) {
 ; CHECK-LABEL: @add_to_sub2(
-; CHECK-NEXT:    [[B:%.*]] = mul i32 [[M:%.*]], 42
-; CHECK-NEXT:    [[C:%.*]] = xor i32 [[B]], -1
-; CHECK-NEXT:    [[D:%.*]] = add i32 [[C]], [[A:%.*]]
-; CHECK-NEXT:    [[E:%.*]] = add i32 [[D]], 1
+; CHECK-NEXT:    [[TMP1:%.*]] = mul i32 [[M:%.*]], -42
+; CHECK-NEXT:    [[E:%.*]] = add i32 [[TMP1]], [[A:%.*]]
 ; CHECK-NEXT:    ret i32 [[E]]
 ;
   %B = mul i32 %M, 42          ; thwart complexity-based ordering
   %C = xor i32 %B, -1
   %D = add i32 %C, %A
   %E = add i32 %D, 1
   ret i32 %E
 }