[InstCombine] add nsw on InstCombineAdd ~X + C --> (C-1) - X

[khei4]

Summary

This is the final step for https://reviews.llvm.org/D146903 .

On transform ~X + C --> (C-1) - X, we can safely attach NSW to (C-1) - X if the 1,2 are satisfied

1. ~X + C has NSW
2. C-1 won't signed overflow

proof: https://alive2.llvm.org/ce/z/ZWmZLv
precommit tests: https://reviews.llvm.org/D152089

This will resolve https://reviews.llvm.org/D146903 's InstCombine part.
Motivational Transformation: https://alive2.llvm.org/ce/z/-_FdJU

[khei4]

Rebase for pre-commit test

[nikic]

proof: https://alive2.llvm.org/ce/z/DXXaoC

This looks more complicated than necessary, just this should be enough: https://alive2.llvm.org/ce/z/ZWmZLv

llvm/test/Transforms/InstCombine/add.ll

391

I think we could have a few additional tests here:

• Negative test with nuw instead of nsw.
• Non-splat vector tests with constants -127, -126 (ok) and -128, -127 (not ok)? This fold handles non-splat vectors, so we should check the overflow behavior there as well.

[khei4]

rebase for tests update

[nikic]

llvm/test/Transforms/InstCombine/add.ll

421

You've adjusted the constants here so it now folds, which doesn't match the TODO comment. Not sure what the intention for this test was.

[khei4]

This looks more complicated than necessary, just this should be enough: https://alive2.llvm.org/ce/z/ZWmZLv

Thanks! Seems cool! I'll put it on description :)

llvm/test/Transforms/InstCombine/add.ll

421

Sorry, I tweaked it not to attach nsw, I'll rebase.

[khei4]

rebase

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (match(Op0, m_ZExt(m_Value(X))) &&
       X->getType()->getScalarSizeInBits() == 1)
     return SelectInst::Create(X, InstCombiner::AddOne(Op1C), Op1);
   // sext(bool) + C -> bool ? C - 1 : C
   if (match(Op0, m_SExt(m_Value(X))) &&
       X->getType()->getScalarSizeInBits() == 1)
     return SelectInst::Create(X, InstCombiner::SubOne(Op1C), Op1);
 
   // ~X + C --> (C-1) - X
-  if (match(Op0, m_Not(m_Value(X))))
-    return BinaryOperator::CreateSub(InstCombiner::SubOne(Op1C), X);
+  if (match(Op0, m_Not(m_Value(X)))) {
+    // ~X + C has NSW and (C-1) won't oveflow => (C-1)-X can have NSW
+    auto *COne = ConstantInt::get(Op1C->getType(), 1);
+    bool WillNotSOV = willNotOverflowSignedSub(Op1C, COne, Add);
+    BinaryOperator *Res =
+        BinaryOperator::CreateSub(ConstantExpr::getSub(Op1C, COne), X);
+    Res->setHasNoSignedWrap(Add.hasNoSignedWrap() && WillNotSOV);
+    return Res;
+  }
 
   // (iN X s>> (N - 1)) + 1 --> zext (X > -1)
   const APInt *C;
   unsigned BitWidth = Ty->getScalarSizeInBits();
   if (match(Op0, m_OneUse(m_AShr(m_Value(X),
                                  m_SpecificIntAllowUndef(BitWidth - 1)))) &&
       match(Op1, m_One()))
     return new ZExtInst(Builder.CreateIsNotNeg(X, "isnotneg"), Ty);

llvm/test/Transforms/InstCombine/add.ll

;
   %B = xor i8 %A, -1
   %C = add i8 %B, 17
   ret i8 %C
 }
 
 ; ~X + -127 and (-128) - X with nsw are equally poisonous
 define i8 @test18_nsw(i8 %A) {
 ; CHECK-LABEL: @test18_nsw(
-; CHECK-NEXT:    [[C:%.*]] = sub i8 -128, [[A:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = sub nsw i8 -128, [[A:%.*]]
 ; CHECK-NEXT:    ret i8 [[C]]
 ;
   %B = xor i8 %A, -1
   %C = add nsw i8 %B, -127
   ret i8 %C
 }
 
 ; nuw couldn't propagate as nsw is.

 define i8 @test18_nsw_overflow(i8 %A) {
 ; CHECK-LABEL: @test18_nsw_overflow(
 ; CHECK-NEXT:    [[C:%.*]] = sub i8 127, [[A:%.*]]
 ; CHECK-NEXT:    ret i8 [[C]]
 ;
   %B = xor i8 %A, -1
   %C = add nsw i8 %B, -128
   ret i8 %C
 }
 
 define <2 x i64> @test18vec(<2 x i64> %A) {
 ; CHECK-LABEL: @test18vec(
 ; CHECK-NEXT:    [[ADD:%.*]] = sub <2 x i64> <i64 1, i64 2>, [[A:%.*]]
 ; CHECK-NEXT:    ret <2 x i64> [[ADD]]
 ;
   %xor = xor <2 x i64> %A, <i64 -1, i64 -1>
   %add = add <2 x i64> %xor, <i64 2, i64 3>
   ret <2 x i64> %add
 }
 
 define <2 x i8> @test18vec_nsw(<2 x i8> %A) {
 ; CHECK-LABEL: @test18vec_nsw(
-; CHECK-NEXT:    [[C:%.*]] = sub <2 x i8> <i8 -124, i8 -125>, [[A:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = sub nsw <2 x i8> <i8 -124, i8 -125>, [[A:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[C]]
 ;
   %B = xor <2 x i8> %A, <i8 -1, i8 -1>
   %C = add nsw <2 x i8> %B, <i8 -123, i8 -124>
   ret <2 x i8> %C
 }
 
 ; TODO: fix ValueTracking overflow check for non-splat vector, could be attached nsw
 ; this shouldn't overflow.
 define <2 x i8> @test18vec_nsw_false(<2 x i8> %A) {
 ; CHECK-LABEL: @test18vec_nsw_false(
 ; CHECK-NEXT:    [[C:%.*]] = sub <2 x i8> <i8 -125, i8 -126>, [[A:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[C]]
 ;
   %B = xor <2 x i8> %A, <i8 -1, i8 -1>
   %C = add nsw <2 x i8> %B, <i8 -124, i8 -125>
   ret <2 x i8> %C
 }
 
 
 define <2 x i8> @test18vec_nuw(<2 x i8> %A) {
 ; CHECK-LABEL: @test18vec_nuw(
 ; CHECK-NEXT:    [[C:%.*]] = sub <2 x i8> <i8 -128, i8 -127>, [[A:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[C]]