Page MenuHomePhabricator

[InstCombine] Canonicalize "and, add", "or, add", "xor, add"
ClosedPublic

Authored by emgullufsen on Aug 3 2022, 10:24 PM.

Details

Summary

Canonicalize

((x + C1) & C2) --> ((x & C2) + C1)     
((x + C1) ^ C2) --> ((x ^ C2) + C1)     
((x + C1) | C2) --> ((x | C2) + C1)

for suitable constants C1 and C2.

Alive2 proofs: add, or --> or, add
add, xor --> xor, add
add, and --> and, add

Diff Detail

Event Timeline

emgullufsen created this revision.Aug 3 2022, 10:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 3 2022, 10:24 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
emgullufsen requested review of this revision.Aug 3 2022, 10:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 3 2022, 10:24 PM

Hadn't run clang-format

emgullufsen retitled this revision from [InstCombine] Canonicalize ((x + C1) & C2) --> ((x & C2) + C1) ((x + C1) & C2) --> ((x & C2) + C1) ((x + C1) & C2) --> ((x & C2) + C1) for suitable constants C1 and C2. to [InstCombine] .Aug 3 2022, 10:36 PM
emgullufsen edited the summary of this revision. (Show Details)
emgullufsen retitled this revision from [InstCombine] to [InstCombine] Canonicalize "and, add", "or, add", "xor, add".
emgullufsen edited the summary of this revision. (Show Details)Aug 3 2022, 10:38 PM

I wasn't sure whether to subsume D130080 or make this revision a child of that one.

Update on top of new negative multiple use tests in and-xor-or.ll

Updated on top of vector tests

Added clarifying comment in test

clang-format

Needed to run update_test_checks.py against add.ll

emgullufsen edited the summary of this revision. (Show Details)Aug 11 2022, 8:32 AM
emgullufsen edited the summary of this revision. (Show Details)
foad added a comment.Aug 23 2022, 7:31 AM

Looks good overall.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1769

The way you've written it is fine. Just remove the comment.

1774

Can you just fold the ! and >= into < please

1783

This can be llvm_unreachable

llvm/test/Transforms/InstCombine/integer-round-up-pow2-alignment.ll
13 ↗(On Diff #451667)

These changes are not significant - it's just update_test_checks choosing a different name for its variables. Could you regenerate the checks for this file first and commit that, and then rebase the current patch?

We need to keep nsw/nuw for add I think.
And it's better to provider alive proof link also.

llvm/test/Transforms/InstCombine/add.ll
726 ↗(On Diff #451667)

I think this code want to get better address pattern for load/store. But don't know why we do this before with this comment.
@spatel this test case is commited on dab8515370c7fd43782e72c46333e801454219cc
do you remember the history about the test ?

nit: please edit the summary with

// (X + C2) | C
// (X + C2) ^ C
// (X + C2) & C
spatel added inline comments.Aug 23 2022, 10:47 AM
llvm/test/Transforms/InstCombine/add.ll
726 ↗(On Diff #451667)

I didn't find any direct reason, but f82c55fa082711f520 inverted the transform and updated the comment. This patch needs to be rebased, so we are not confusing the diffs.

foad added a comment.Aug 24 2022, 2:42 AM

We need to keep nsw/nuw for add I think.

Agreed, good point.

emgullufsen edited the summary of this revision. (Show Details)Aug 24 2022, 8:06 AM
emgullufsen updated this revision to Diff 455246.EditedAug 24 2022, 9:04 AM

Rebase & Address comments

emgullufsen marked 3 inline comments as done.Aug 24 2022, 9:05 AM
emgullufsen edited the summary of this revision. (Show Details)
emgullufsen added a comment.EditedAug 24 2022, 9:14 AM

This patch now does not affect integer-round-up-pow2-alignment.ll (since those changes merged via rGf82c55fa082711f520a7359393b483956b69bf08). So, the NFC changes (changes of variable names) that update_test_checks would make don't have to be addressed at this time (I don't think). I did pull those NFC changes to this test out anyway as D132564, but as said I don't think this needs to be messed with just now.

This seems right, but can you verify with Alive2 and add the links to the patch summary.
If I modeled the code correctly, it looks like this for or/xor:
https://alive2.llvm.org/ce/z/BhAeCl
...and needs a small adjustment for 'and'.

emgullufsen added a comment.EditedFri, Aug 26, 9:24 AM

This seems right, but can you verify with Alive2 and add the links to the patch summary.
If I modeled the code correctly, it looks like this for or/xor:
https://alive2.llvm.org/ce/z/BhAeCl
...and needs a small adjustment for 'and'.

Oh shoot I had meant to include alive2 proofs - sorry for that (and thank you for or/xor proofs) - will get patch summary updated.

emgullufsen edited the summary of this revision. (Show Details)Fri, Aug 26, 10:03 AM
spatel accepted this revision.Fri, Aug 26, 10:49 AM

LGTM

This revision is now accepted and ready to land.Fri, Aug 26, 10:49 AM
emgullufsen edited the summary of this revision. (Show Details)Fri, Aug 26, 11:06 AM
This revision was landed with ongoing or failed builds.Fri, Aug 26, 11:07 AM
This revision was automatically updated to reflect the committed changes.
emgullufsen reopened this revision.Fri, Aug 26, 11:28 AM
This revision is now accepted and ready to land.Fri, Aug 26, 11:28 AM
emgullufsen edited the summary of this revision. (Show Details)

Sorry for the failed test - I ran update_test_checks against test/Transforms/InstCombine/freeze.ll,
and the changes I verified using Alive2 https://alive2.llvm.org/ce/z/4ABLcz

emgullufsen requested review of this revision.Fri, Aug 26, 12:18 PM
spatel accepted this revision.Fri, Aug 26, 1:17 PM

To confirm, you just missed updating a test, right?
Still LGTM - the extra test diff is an improvement. :)

This revision is now accepted and ready to land.Fri, Aug 26, 1:17 PM

To confirm, you just missed updating a test, right?
Still LGTM - the extra test diff is an improvement. :)

Yes I just missed updating a test that I should have noticed, that actually caused bot failure. But freeze.ll seems to be the only one I missed - check-llvm results look good now.

emgullufsen added a comment.EditedFri, Aug 26, 2:07 PM

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

No need. I reverted because of a broken test, if that's been fixed, your LGTM stands.

Thanks for reverting @reames - when you have a second maybe you could please have a look over this updated patch?

No need. I reverted because of a broken test, if that's been fixed, your LGTM stands.

Cool I see - I didn't think I needed to ask for review from reverting dev from Developer Policy, but just wanted to be sure I guess. Thanks again to you and to @spatel for help with proofs and review. Will be more careful with tests in the future.

bcl5980 added inline comments.Fri, Aug 26, 10:47 PM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1810

I still insist we should add the nsw/nuw flags here as this transform is really easy case to pass the flags.

spatel added inline comments.Tue, Aug 30, 4:48 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1810

Yes - if we can keep flags, we should do that. @emgullufsen - can you create tests/patch for that?