[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

640 ↗

(On Diff #528171)

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 ↗

(On Diff #528267)

curret -> current

[khei4]

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

207 ↗

(On Diff #528267)

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, C-(X+C2), (X+C2) never overflow=> (C-C2)-X never overflow
+      BinaryOperator *Res =
+          BinaryOperator::CreateSub(ConstantExpr::getSub(C, C2), X);
+      auto *OBO1 = cast<OverflowingBinaryOperator>(Op1);
+      Res->setHasNoSignedWrap(I.hasNoSignedWrap() &&
+                              OBO1->hasNoUnsignedWrap() &&
+                              willNotOverflowSignedSub(C, C2, *Res));
+      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)) {