This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] try to fold the expression "(A & ~B) + B" to "A | B"
AbandonedPublic

Authored by spatel on Jun 28 2021, 4:41 AM.

Details

Summary

Summary

Since llvm will generate the following ir:
define i32 @and_to_xor1(i32 %0, i32 %1) local_unnamed_addr #0 {
   %3 = shl nsw i32 %0, 1
   %4 = mul nsw i32 %1, %0
   %5 = xor i32 %4, -1
   %6 = and i32 %3, %5
   %7 = add nsw i32 %6, %4
   ret i32 %7
 }

but InstCombine can not simplify this code shape.
So I use this patch to achieve this.

Test Plan:

check-llvm

Diff Detail

Event Timeline

dongAxis1944 created this revision.Jun 28 2021, 4:41 AM
dongAxis1944 requested review of this revision.Jun 28 2021, 4:41 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 28 2021, 4:41 AM

The missing fold here is: https://alive2.llvm.org/ce/z/7uIb0B (i.e. it should go into haveNoCommonBitsSet())
And this will automagically fold to or, not xor: https://godbolt.org/z/6svT3vc44

The missing fold here is: https://alive2.llvm.org/ce/z/7uIb0B (i.e. it should go into haveNoCommonBitsSet())
And this will automagically fold to or, not xor: https://godbolt.org/z/6svT3vc44

Sorry for my mistake, I just missing the right expression.

dongAxis1944 retitled this revision from [InstCombine] try to fold the expression "(A & ~B) + B" to "A ^ B" to [InstCombine] try to fold the expression "(A & ~B) + B" to "A | B".

modify code , the original code is wrong

fix wrong comment

This pattern (A & ~B) op B should be matched in llvm::haveNoCommonBitsSet() in ValueTracking.cpp.

add pattern in valuetrack

spatel added inline comments.Jun 28 2021, 8:26 AM
llvm/test/Transforms/InstCombine/and-to-xor.ll
8 ↗(On Diff #354895)
  1. The tests should be minimized - only instructions in the most basic pattern need to be here, so something like:

https://alive2.llvm.org/ce/z/NrJRbF

  1. Use llvm/utils/update_test_checks.py to auto-generate the CHECK lines.
  1. You can probably add these tests in the same file where existing haveNoCommonBitSet patterns are tested (disable the existing transform and see which tests fail).
dongAxis1944 updated this revision to Diff 355120.EditedJun 28 2021, 11:58 PM

@spatel thanks, I update the case, and I prefer use the new file, because the old case might not be clear to find I think.

spatel added inline comments.Jun 29 2021, 4:37 AM
llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
5

There are 4 commuted variations of this pattern, so we should have a test for each. Other transforms will try to normalize the code structure, so the tests will have to overcome that to provide full coverage.

Search for "thwart complexity-based canonicalization" in the test dir for examples.

You may vary the value types across those 4 tests for more coverage as well (try unusual widths or vectors).

5

Remove "dso_local" and mangling artifacts from the function name.

It's easier to read the tests if the values are named the same as in the code comment ("A" and "B" in this case).

spatel added inline comments.Jun 29 2021, 4:39 AM
llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
16

If I'm seeing it correctly, this test does not change with this patch. Why is it included?

remove useless ut

dongAxis1944 added inline comments.Jun 29 2021, 7:47 AM
llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
5

thanks., I will update later

address the comment

dongAxis1944 marked 3 inline comments as done.Jun 30 2021, 6:20 AM

format the patch

address comment

spatel added a comment.Jul 9 2021, 1:07 PM

gentle ping @spatel @lebedev.ri

I don't think you've accounted for commutation in the tests. Did you see the existing test examples that have the comment "thwart complexity-based canonicalization"?
Do you have commit access? If so, please commit the tests only without the code change (and so with baseline CHECK lines), so we can confirm.

llvm/test/Analysis/ValueTracking/known-non-common-bits.ll
5

Remove mangling artifacts (_Z11, 1ii) from all function names.

lebedev.ri resigned from this revision.Jan 12 2023, 5:23 PM

This review seems to be stuck/dead, consider abandoning if no longer relevant.

Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 5:23 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
spatel commandeered this revision.Jan 16 2023, 5:26 AM
spatel edited reviewers, added: dongAxis1944; removed: spatel.
spatel abandoned this revision.Jan 16 2023, 5:26 AM