[InstCombine] add overflow checking on AddSub `C-(X+C2) --> (C-C2)-X`

[khei4]

Summary

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

1. A:= (X+C2) has NSW
2. C-A has NSW
3. C-C2 won't signed overflow

proof: https://alive2.llvm.org/ce/z/S4rQUS
pre-commit tests: https://reviews.llvm.org/D152091

[khei4]

rebase

[khei4]

This doesn't seem working.

Res->setHasNoSignedWrap(I.hasNoSignedWrap() &&
                             OBO1->hasNoUnsignedWrap() &&
                             willNotOverflowSignedSub(C, C2, *Res));

[nikic]

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

I don't think this proof is correct, because the sub nsw i8 %c1, %c2 will already be poison on overflow, so your assume doesn't do what you intended. You probably want something like this: https://alive2.llvm.org/ce/z/S4rQUS

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2004

hasNoUnsignedWrap -> hasNoSignedWrap

2005

*Res should be I here.

[khei4]

Thank you for the review!

I don't think this proof is correct, because the sub nsw i8 %c1, %c2 will already be poison on overflow,

Seems so! The original assumption seemed to allow all c1 and c2. Thanks!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2004

Ah... Thanks!

2005

Seems reasonable!

[khei4]

apply feedback

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2002

given that C-C2 is a constexpr do the flag matter at all? If not can you drop them from the constexpr, they just seem noisey.

2004

Nit:
Res->setHasNoSignedWrap(I.hasNoSignedWrap() && OBO1->hasNoSignedWrap() && HasNSW)

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll

746

Can you precommit the tests? Also can you add a failure test s.t one of the 3 conditions aren't met for each condition.

[khei4]

Apply feedback from @goldstein.w.n

[khei4]

Thank you for the review!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

2002

Thank you for a good catch! In this case, giving overflow checking of C - C2 will be a problem for C-(X+C2) and (X+C2) will signed wrapped and C - C2 overflowcase!

[khei4]

update tests

[khei4]

remove noise test

[nikic]

LGTM

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll

207

curret -> current

[khei4]

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll

207

Thanks! This will be fixed in the pre-commit test commit!

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (Instruction *R = factorizeMathWithShlOps(I, Builder))
     return R;
 
   Constant *C;
   if (match(Op0, m_ImmConstant(C))) {
     Value *X;
     Constant *C2;
 
     // C-(X+C2) --> (C-C2)-X
-    if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2))))
-      return BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
+    if (match(Op1, m_Add(m_Value(X), m_ImmConstant(C2)))) {
+      // C-C2 never overflow, and C-(X+C2), (X+C2) has NSW
+      // => (C-C2)-X can have NSW
+      bool WillNotSOV = willNotOverflowSignedSub(C, C2, I);
+      BinaryOperator *Res =
+          BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
+      auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
+      Res->setHasNoSignedWrap(I.hasNoSignedWrap() && OBO1->hasNoSignedWrap() &&
+                              WillNotSOV);
+      return Res;
+    }
   }
 
   auto TryToNarrowDeduceFlags = [this, &I, &Op0, &Op1]() -> Instruction * {
     if (Instruction *Ext = narrowMathIfNoOverflow(I))
       return Ext;
 
     bool Changed = false;
     if (!I.hasNoSignedWrap() && willNotOverflowSignedSub(Op0, Op1, I)) {

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll

 ;
   %t0 = add i32 %arg, 8
   %t1 = sub i32 2, %t0
   ret i32 %t1
 }
 
 define i8 @add_nsw_const_const_sub_nsw(i8 %arg) {
 ; CHECK-LABEL: @add_nsw_const_const_sub_nsw(
-; CHECK-NEXT:    [[T1:%.*]] = sub i8 -128, [[ARG:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = sub nsw i8 -128, [[ARG:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = add nsw i8 %arg, 1
   %t1 = sub nsw i8 -127, %t0
   ret i8 %t1
 }
 
 define i8 @add_nsw_const_const_sub(i8 %arg) {

 ; CHECK-NEXT:    [[T1:%.*]] = sub i8 -128, [[ARG:%.*]]
 ; CHECK-NEXT:    ret i8 [[T1]]
 ;
   %t0 = add i8 %arg, 1
   %t1 = sub nuw i8 -127, %t0
   ret i8 %t1
 }
 
-
 define <2 x i8> @non_splat_vec_add_nsw_const_const_sub_nsw_not_ov1(<2 x i8> %arg) {
 ; CHECK-LABEL: @non_splat_vec_add_nsw_const_const_sub_nsw_not_ov1(
-; CHECK-NEXT:    [[T1:%.*]] = sub <2 x i8> <i8 -2, i8 -126>, [[ARG:%.*]]
+; CHECK-NEXT:    [[T1:%.*]] = sub nsw <2 x i8> <i8 -127, i8 -126>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[T1]]
 ;
-  %t0 = add nsw <2 x i8> %arg, <i8 1, i8 0>
-  %t1 = sub nsw <2 x i8> <i8 -1, i8 -126>, %t0
+  %t0 = add nsw <2 x i8> %arg, <i8 2, i8 0>
+  %t1 = sub nsw <2 x i8> <i8 -125, i8 -126>, %t0
   ret <2 x i8> %t1
 }
 
 
 ; TODO: We can add nsw on sub, current Value Tracking use [max element,min element] constant range, to check overflow for vector?
 define <2 x i8> @non_splat_vec_add_nsw_const_const_sub_nsw_not_ov2(<2 x i8> %arg) {
 ; CHECK-LABEL: @non_splat_vec_add_nsw_const_const_sub_nsw_not_ov2(
 ; CHECK-NEXT:    [[T1:%.*]] = sub <2 x i8> <i8 -126, i8 -128>, [[ARG:%.*]]
 ; CHECK-NEXT:    ret <2 x i8> [[T1]]
 ;
   %t0 = add nsw <2 x i8> %arg, <i8 1, i8 2>
   %t1 = sub nsw <2 x i8> <i8 -125, i8 -126>, %t0
   ret <2 x i8> %t1

 ; CHECK-NEXT:    call void @use(i8 [[SUB]])
 ; CHECK-NEXT:    [[R:%.*]] = add i8 [[SUB]], [[Y:%.*]]
 ; CHECK-NEXT:    ret i8 [[R]]
 ;
   %sub = sub i8 1, %x
   call void @use(i8 %sub)
   %r = add i8 %sub, %y
   ret i8 %r
 }