This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by khei4 on Jun 3 2023, 9:31 AM.

Details

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

Diff Detail

Event Timeline

khei4 created this revision.Jun 3 2023, 9:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 3 2023, 9:31 AM
khei4 requested review of this revision.Jun 3 2023, 9:31 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 3 2023, 9:31 AM
khei4 updated this revision to Diff 528115.Jun 3 2023, 9:56 AM
khei4 retitled this revision from (WIP) [InstCombine] add overflow checking on AddSub to [InstCombine] add overflow checking on AddSub `C-(X+C2) --> (C-C2)-X`.
khei4 edited the summary of this revision. (Show Details)
khei4 added a reviewer: spatel.
khei4 edited the summary of this revision. (Show Details)
khei4 added a comment.Jun 3 2023, 10:14 AM

This doesn't seem working.

Res->setHasNoSignedWrap(I.hasNoSignedWrap() &&
                             OBO1->hasNoUnsignedWrap() &&
                             willNotOverflowSignedSub(C, C2, *Res));
nikic added a comment.Jun 3 2023, 11:41 AM

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 added a comment.Jun 3 2023, 5:54 PM

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 updated this revision to Diff 528171.Jun 3 2023, 5:55 PM

apply feedback

goldstein.w.n added inline comments.
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 edited the summary of this revision. (Show Details)Jun 3 2023, 9:00 PM
khei4 updated this revision to Diff 528184.Jun 3 2023, 9:37 PM
khei4 edited the summary of this revision. (Show Details)

Apply feedback from @goldstein.w.n

khei4 added a comment.Jun 3 2023, 9:38 PM

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 edited the summary of this revision. (Show Details)Jun 4 2023, 7:22 PM
khei4 edited the summary of this revision. (Show Details)
khei4 updated this revision to Diff 528266.Jun 4 2023, 8:29 PM
khei4 edited the summary of this revision. (Show Details)

update tests

khei4 updated this revision to Diff 528267.Jun 4 2023, 8:31 PM

remove noise test

nikic accepted this revision.Jun 4 2023, 11:49 PM

LGTM

llvm/test/Transforms/InstCombine/addsub-constant-folding.ll
207 ↗(On Diff #528267)

curret -> current

This revision is now accepted and ready to land.Jun 4 2023, 11:49 PM
khei4 added inline comments.Jun 5 2023, 3:33 AM
llvm/test/Transforms/InstCombine/addsub-constant-folding.ll
207 ↗(On Diff #528267)

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