[InstCombine] don't lose nsw/nuw from add by converting to xor

[spatel]

Summary

I was looking at an improvement to InstSimplify when I noticed that this add fold in InstCombine was preventing icmp simplifies.

There's a later fold that special-cases (add (xor with signbit), C), so I don't think we're losing anything by limiting this.

'test20' and 'xor_sign_bit' in add.ll verify that the later fold still works, so there are no regressions in existing tests.

[efriedma]

We don't want to go down the path of forbidding optimizations on add/sub because we can deduce the operation doesn't overflow. There's been a lot of activity recently surrounding the representation of predicates/assertions/etc.; the right solution probably lies in that direction.

[spatel]

In D29729#671286, @efriedma wrote:

We don't want to go down the path of forbidding optimizations on add/sub because we can deduce the operation doesn't overflow. There's been a lot of activity recently surrounding the representation of predicates/assertions/etc.; the right solution probably lies in that direction.

Let me make sure I'm not completely lost. I'm working on an instcombine icmp+add patch that relies on nsw to eliminate the add:
https://godbolt.org/g/yzoxeY

Should I not pursue that because the transform relies on nsw?

[efriedma]

instcombine is allowed to use nsw to permit transformations which would otherwise be illegal. instcombine should not avoid transformations for fear of dropping nsw or other metadata.

[spatel]

In D29729#671331, @efriedma wrote:

instcombine is allowed to use nsw to permit transformations which would otherwise be illegal. instcombine should not avoid transformations for fear of dropping nsw or other metadata.

Thanks!

So for this patch, is instcombine behaving as expected already? Ie, it's ok to drop the nsw, some other pass has the responsibility to optimize this code:
https://godbolt.org/g/ezOlu6

Or should instcombine attempt to preserve the nsw despite changing the add into xor? The current mechanism would be to add an icmp+llvm.assume? Any better ideas?

[efriedma]

Fundamentally, many optimizations which simplify code involve dropping information which could be derived from the unoptimized code; we don't attempt to keep around all possible information which could be used by the optimizer. For example, combining nsw "a + 1 - 1" to "a" drops the information that "a" is not INT_MAX, and that's fine.

You can't actually use llvm.assume to record nsw information because nsw doesn't act like other metadata: overflow produces poison rather than undefined behavior.

[spatel]

Patch updated:
If llvm.assume can't be used to solve this, I don't know of an existing way to do it, so I'm making this an NFC documentation patch for the current behavior.

[sanjoy]

I think we can get the best of both worlds here -- both X +nsw INT_MIN and X +nuw INT_MIN can be transformed to X | INT_MIN. http://rise4fun.com/Alive/ZpV

And then (X | INT_MIN) s< 0 can be folded to false.

[Edit: minor typo fixed]

[spatel]

Patch updated:
As suggested by Sanjoy, use 'or' rather than 'xor' when we have {nuw,nsw}. This allows the cmp tests to succeed.
There's a regression in the first add test because we don't recognize the larger pattern, but I've marked that with FIXME since this is still an overall improvement IMO.

[sanjoy]

test/Transforms/InstCombine/add.ll

252

Can we add a simple peephole to not regress this case? I.e. (xor SIGN_BIT (add nsw X SIGN_BIT)) to X?

(I'm fine doing that in an immediately following change and not in this change specifically).

test/Transforms/InstCombine/icmp-add.ll

226

Why not just delete the comment?

[sanjoy]

Other than that LGTM.

[spatel]

test/Transforms/InstCombine/add.ll

252

Sure - I didn't know if combining those 2 steps into 1 patch would be welcome, but it makes sense to not introduce a known regression.

test/Transforms/InstCombine/icmp-add.ll

226

I'd prefer to leave it here to supply the motivation. I often see tests like this that would seem to belong in InstSimplify rather than InstCombine, and I can't tell if that's intentional or just an artifact of LLVM optimization history (and therefore, the test is redundant and removeable).

[spatel]

test/Transforms/InstCombine/add.ll

252

rL295573

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Value *V = SimplifyAddInst(LHS, RHS, I.hasNoSignedWrap(),
     return replaceInstUsesWith(I, V);
 
    // (A*B)+(A*C) -> A*(B+C) etc
   if (Value *V = SimplifyUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
 
   const APInt *Val;
   if (match(RHS, m_APInt(Val))) {
+    if (Val->isSignBit()) {
+      // If wrapping is not allowed, then the addition must set the sign bit:
+      // X + (signbit) --> X | signbit
+      if (I.hasNoSignedWrap() || I.hasNoUnsignedWrap())
+        return BinaryOperator::CreateOr(LHS, RHS);
+
+      // If wrapping is allowed, then the addition flips the sign bit of LHS:
       // X + (signbit) --> X ^ signbit
-    if (Val->isSignBit())
       return BinaryOperator::CreateXor(LHS, RHS);
+    }
 
     // Is this add the last step in a convoluted sext?
     Value *X;
     const APInt *C;
     if (match(LHS, m_ZExt(m_Xor(m_Value(X), m_APInt(C)))) &&
         C->isMinSignedValue() &&
         C->sext(LHS->getType()->getScalarSizeInBits()) == *Val) {
       // add(zext(xor i16 X, -32768), -32768) --> sext X

test/Transforms/InstCombine/add.ll

 ; CHECK-NEXT:    [[V:%.*]] = select i1 %C, i32 1123, i32 133
 ; CHECK-NEXT:    ret i32 [[V]]
 ;
   %A = select i1 %C, i32 1000, i32 10
   %V = add i32 %A, 123
   ret i32 %V
 }
 
-; Add of sign bit -> xor of sign bit.
+; With NSW, add of sign bit -> or of sign bit.
+; FIXME: This should be 'ret %x' because we know that %x's sign bit must be set already.
 
 define i32 @test20(i32 %x) {
 ; CHECK-LABEL: @test20(
-; CHECK-NEXT:    ret i32 %x
+; CHECK-NEXT:    [[Z:%.*]] = or i32 %x, -2147483648
+; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %y = xor i32 %x, -2147483648
   %z = add nsw i32 %y, -2147483648
   ret i32 %z
 }
 
 define i32 @xor_sign_bit(i32 %x) {
 ; CHECK-LABEL: @xor_sign_bit(
 ; CHECK-NEXT:    [[ADD:%.*]] = add i32 %x, -2147483606
 ; CHECK-NEXT:    ret i32 [[ADD]]
 ;
   %xor = xor i32 %x, 2147483648
   %add = add i32 %xor, 42
   ret i32 %add
 }
 
-; Lose no-wrap info by converting to xor? %x is known non-negative
-; here, but not after converting to xor.
+; No-wrap info allows converting the add to 'or'.
 
 define i8 @add_nsw_signbit(i8 %x) {
 ; CHECK-LABEL: @add_nsw_signbit(
-; CHECK-NEXT:    [[Y:%.*]] = xor i8 %x, -128
+; CHECK-NEXT:    [[Y:%.*]] = or i8 %x, -128
 ; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %y = add nsw i8 %x, -128
   ret i8 %y
 }
 
-; Lose no-wrap info by converting to xor? %x is known non-negative
-; (x < 128 unsigned), but not after converting to xor.
+; No-wrap info allows converting the add to 'or'.
 
 define i8 @add_nuw_signbit(i8 %x) {
 ; CHECK-LABEL: @add_nuw_signbit(
-; CHECK-NEXT:    [[Y:%.*]] = xor i8 %x, -128
+; CHECK-NEXT:    [[Y:%.*]] = or i8 %x, -128
 ; CHECK-NEXT:    ret i8 [[Y]]
 ;
   %y = add nuw i8 %x, 128
   ret i8 %y
 }
 
 define i1 @test21(i32 %x) {
 ; CHECK-LABEL: @test21(

test/Transforms/InstCombine/icmp-add.ll

 ; CHECK-LABEL: @nsw_slt5_ov(
 ; CHECK-NEXT:    ret i1 true
 ;
   %b = add nsw i8 %a, -100
   %c = icmp slt i8 %b, 28
   ret i1 %c
 }
 
-; FIXME: InstCombine should not lose wrapping information by changing the add to xor.
+; InstCombine should not thwart this opportunity to simplify completely.
 
 define i1 @slt_zero_add_nsw_signbit(i8 %x) {
 ; CHECK-LABEL: @slt_zero_add_nsw_signbit(
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 %x, -1
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = add nsw i8 %x, -128
   %z = icmp slt i8 %y, 0
   ret i1 %z
 }
 
-; FIXME: InstCombine should not lose wrapping information by changing the add to xor.
+; InstCombine should not thwart this opportunity to simplify completely.
 
 define i1 @slt_zero_add_nuw_signbit(i8 %x) {
 ; CHECK-LABEL: @slt_zero_add_nuw_signbit(
-; CHECK-NEXT:    [[Z:%.*]] = icmp sgt i8 %x, -1
-; CHECK-NEXT:    ret i1 [[Z]]
+; CHECK-NEXT:    ret i1 true
 ;
   %y = add nuw i8 %x, 128
   %z = icmp slt i8 %y, 0
   ret i1 %z
 }