[InstCombine] Fix missing nsw flag when fold -(x-y) to y-x

[bcl5980]

Summary

Use CreateNSWSub instead of CreateSub if possible

[nikic]

This is correct if both subs are nsw: https://alive2.llvm.org/ce/z/r6UV8Q But not if only one of them is: https://alive2.llvm.org/ce/z/3_2BDj

[bcl5980]

Only neg is nsw also can createNSWSub
Neg by sub 0 case:
https://alive2.llvm.org/ce/z/KZLr8T
https://alive2.llvm.org/ce/z/lHJc-f
https://alive2.llvm.org/ce/z/pgH3Wd
https://alive2.llvm.org/ce/z/ZwVCtN

Neg by mul -1 case:
https://alive2.llvm.org/ce/z/BwMPtA
https://alive2.llvm.org/ce/z/Vn4pjh
https://alive2.llvm.org/ce/z/rYSowr
https://alive2.llvm.org/ce/z/fA587w

[lebedev.ri]

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

247

CreateSub(I->getOperand(1), I->getOperand(0), I->getName() + ".neg", false, I->hasNoSignedWrap() && HasNSW); ?

[bcl5980]

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013
Maybe we can enable it when IsTrulyNegation ? Abandon is also OK for me.

[lebedev.ri]

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

[bcl5980]

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

Thanks for the detail explaination. So if we really want this work, it should be

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

or we need to trace every recursive instruction is also NSW, am I right?

[lebedev.ri]

In D122299#3402164, @bcl5980 wrote:

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

In D122299#3402130, @lebedev.ri wrote:

In D122299#3402088, @bcl5980 wrote:

In D122299#3402030, @lebedev.ri wrote:

Must we do this? I was really hoping we wouldn't.
Does this actually unblock some measurable improvement?

Consider: https://alive2.llvm.org/ce/z/XYfMSm
Both subs have NSW, so i believe the code will now produce: https://alive2.llvm.org/ce/z/vUseE6

It comes from here https://reviews.llvm.org/D122013

Maybe we can enable it when IsTrulyNegation ?

Oh, hm, that is also a required precondition apparently: https://alive2.llvm.org/ce/z/c9i8Go
But even then, the really big problem for NSW preservation is that every instruction inbetween that we manage to negate through affects the NSW: https://alive2.llvm.org/ce/z/4A--JC

Abandon is also OK for me.

Thanks for the detail explaination. So if we really want this work, it should be

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

or we need to trace every recursive instruction is also NSW, am I right?

I believe that is the idea, yes.

[bcl5980]

Thanks again @lebedev.ri. I will update the code to

bool NSW = I->hasNoSignedWrap() && HasNSW && IsTrulyNegation && Depth == 0;
return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                         I->getName() + ".neg", false, NSW);

but if there is no other comments I prefer to abandon it.

[bcl5980]

only depth == 0 enable nsw flag

[spatel]

I'm fine with abandoning the code change. I just wanted to make sure we were not miscompiling in D122013.

I would commit the tests anyway with some comments or a link back to this review (in case this comes up again in the future in some other context).

llvm/lib/Transforms/InstCombine/InstCombineNegator.cpp

default:
     break; // Other instructions require recursive reasoning.
   }
 
   if (I->getOpcode() == Instruction::Sub &&
       (I->hasOneUse() || match(I->getOperand(0), m_ImmConstant()))) {
     // `sub` is always negatible.
     // However, only do this either if the old `sub` doesn't stick around, or
     // it was subtracting from a constant. Otherwise, this isn't profitable.
+    if (I->hasNoSignedWrap())
+      return Builder.CreateNSWSub(I->getOperand(1), I->getOperand(0),
+                                  I->getName() + ".neg");
     return Builder.CreateSub(I->getOperand(1), I->getOperand(0),
                              I->getName() + ".neg");
   }
 
   // Some other cases, while still don't require recursion,
   // are restricted to the one-use case.
   if (!V->hasOneUse())
     return nullptr;
 
   switch (I->getOpcode()) {
   case Instruction::And: {
     Constant *ShAmt;

llvm/test/Transforms/InstCombine/nsw.ll

 ; CHECK-NEXT:    [[T3:%.*]] = mul <vscale x 2 x i64> [[XX]], shufflevector (<vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer)
 ; CHECK-NEXT:    ret <vscale x 2 x i64> [[T3]]
 ;
   %xx = zext <vscale x 2 x i8> %z to <vscale x 2 x i64>
   %shuf = shufflevector <vscale x 2 x i64> insertelement (<vscale x 2 x i64> undef, i64 3, i32 0), <vscale x 2 x i64> zeroinitializer, <vscale x 2 x i32> zeroinitializer
   %t3 = mul <vscale x 2 x i64> %shuf, %xx
   ret <vscale x 2 x i64> %t3
 }
+
+define i32 @neg_sub_nsw(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub_nsw(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub nsw i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub nsw i32 %a, %b
+  %d = sub i32 0, %c
+  ret i32 %d
+}
+
+define i32 @neg_sub(i32 %a, i32 %b) {
+; CHECK-LABEL: @neg_sub(
+; CHECK-NEXT:    [[C_NEG:%.*]] = sub i32 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i32 [[C_NEG]]
+;
+  %c = sub i32 %a, %b
+  %d = sub i32 0, %c
+  ret i32 %d
+}