[ValueTracking] Checking haveNoCommonBitsSet for (x & y) and ~(x | y)

[ChuanqiXu]

Summary

This one tries to fix: https://github.com/llvm/llvm-project/issues/53357.

Simply, this one would check (x & y) and ~(x | y) in haveNoCommonBitsSet. Since they shouldn't have common bits (we could traverse the case by enumerating), and we could convert this one to (x & y) | ~(x | y) . Then the compiler could handle it in InstCombineAndOrXor.
Further more, since ((x & y) + (~x & ~y)) would be converted to ((x & y) + ~(x | y)), this patch would fix it too.

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

[nikic]

llvm/test/Transforms/InstCombine/pr53357.ll

2

The check lines don't look like update_test_checks output.

[ChuanqiXu]

llvm/test/Transforms/InstCombine/pr53357.ll

2

My bad, I just copied this one from other tests. Do you think what should I do? Remove this one simply?

[ChuanqiXu]

llvm/test/Transforms/InstCombine/pr53357.ll

2

I found several tests contain the line. For example: https://github.com/llvm/llvm-project/commit/732a90da785de2f61dbbf09d6c5fe55937d194b6 and https://github.com/llvm/llvm-project/commit/fc8f1e4419d338a347bade7cfc76f73052f00739. And I add it for consistency. Do you think we need to remove them?

[xbolva00]

llvm/test/Transforms/InstCombine/pr53357.ll

2

You should remove current checks and use that script to generate them properly.

[lebedev.ri]

Please fix the patch's description.
Should this go into have no common bits check instead?

[ChuanqiXu]

Address comments.

[ChuanqiXu]

In D118094#3268554, @lebedev.ri wrote:

Please fix the patch's description.

Do you mean the URL in the description? I would delete it when this one get committed.

Should this go into have no common bits check instead?

I don't understand why this could go into "have no common bits". Since (x & y) and ~(x | y) could have common bits 0 if x is 1 and y is 0. Did I misunderstand something?

llvm/test/Transforms/InstCombine/pr53357.ll

2

Thanks! I didn't know this before. I wrote all the tests by hand in the past.

[ChuanqiXu]

Update diff. I updated a out dated one last time. Sorry

[RKSimon]

llvm/test/Transforms/InstCombine/pr53357.ll

7

Can we remove the dso_local and noundef attributes?

[ChuanqiXu]

Address comments

[RKSimon]

please can you add some vector tests as well?

[ChuanqiXu]

In D118094#3271975, @RKSimon wrote:

please can you add some vector tests as well?

I would love to. If there is any examples I could refer to?

[lebedev.ri]

In D118094#3268592, @ChuanqiXu wrote:

In D118094#3268554, @lebedev.ri wrote:

Please fix the patch's description.

Do you mean the URL in the description? I would delete it when this one get committed.

Should this go into have no common bits check instead?

I don't understand why this could go into "have no common bits". Since (x & y) and ~(x | y) could have common bits 0 if x is 1 and y is 0. Did I misunderstand something?

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

[RKSimon]

llvm/test/Transforms/InstCombine/pr53357.ll

61

For examples (the undef version is an alternative you could use occasionally to show the NOT matching still works):

define <2 x i32> @src4_vec(<2 x i32> %0, <2 x i32> %1) {
  %3 = xor <2 x i32> %0, <i32 -1, i32 -1>
  %4 = xor <2 x i32> %1, <i32 -1, i32 -1>
  %5 = and <2 x i32> %3, %4
  %6 = and <2 x i32> %1, %0
  %7 = add <2 x i32> %5, %6
  ret <2 x i32> %7
}

define <2 x i32> @src4_vec_undef(<2 x i32> %0, <2 x i32> %1) {
  %3 = xor <2 x i32> %0, <i32 -1, i32 undef>
  %4 = xor <2 x i32> %1, <i32 -1, i32 -1>
  %5 = and <2 x i32> %3, %4
  %6 = and <2 x i32> %1, %0
  %7 = add <2 x i32> %5, %6
  ret <2 x i32> %7
}

[ChuanqiXu]

Implement in haveNoCommonBitsSet and add tests.

[ChuanqiXu]

In D118094#3272175, @lebedev.ri wrote:

In D118094#3268592, @ChuanqiXu wrote:

In D118094#3268554, @lebedev.ri wrote:

Please fix the patch's description.

Do you mean the URL in the description? I would delete it when this one get committed.

Should this go into have no common bits check instead?

I don't understand why this could go into "have no common bits". Since (x & y) and ~(x | y) could have common bits 0 if x is 1 and y is 0. Did I misunderstand something?

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

Oh, I made a basic mistake before. It should be haveNoCommonBits. Thanks for reminding me.

llvm/test/Transforms/InstCombine/pr53357.ll

61

Got it. Thanks!

[spatel]

llvm/test/Transforms/InstCombine/pr53357.ll

34

This is logically equivalent to the previous test; the difference is purely one of variable names, not code patterns.
But I think we are missing a test for a pattern where the 'and' is RHS (operand 1) of the 'add', so you can probably adjust it to cover that case.

Note that you may need to add extra instructions to force the IR into the form that you are trying to test. Search for "thwart complexity-based canonicalization" in other files in the instcombine test directory for examples.

Please commit/push these tests with baseline CHECK lines as a preliminary commit to this patch, so we can be sure that we are testing the expected patterns.

[ChuanqiXu]

Address comments.

llvm/test/Transforms/InstCombine/pr53357.ll

34

Thanks for the guide. I've commit the tests in: https://github.com/llvm/llvm-project/commit/1391f91b1f62b9510e4b71737aac2b45d0c4d6cd

[spatel]

llvm/lib/Analysis/ValueTracking.cpp

290 ↗

(On Diff #406320)

If I'm seeing it correctly, these lines could use "m_And" rather than "m_c_And"?

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

This test does not add any value to the previous test. Let's try to simplify things.

IIUC, there are exactly 4 commutative patterns that we want to match:

(x & y) + ~(x | y)
(x & y) + ~(y | x) 
~(x | y) + (x & y) 
~(y | x) + (x & y)

(We can swap the names of x and y, and it doesn't change any logic in the matching code.)

1. Create tests that correspond to those patterns (including using the same value names as in the test comments):

; (x & y) + ~(x | y)
define i32 @no_common_bits_and_nor(i32 %x, i32 %y) {
  %and = and i32 %x, %y
  %or = or i32 %x, %y
  %nor = xor i32 %or, -1
  %r = add i32 %and, %nor
  ret i32 %r
}

2. You can vary the types while checking the commutes, so some of the tests can use vectors (with or without an undef in the 'not' constant).

3. I'm not sure what the tests with extra 'not' instructions are showing. As we can see in the baseline CHECK lines, those are transformed before we reach the transform in this patch. If we want to show that this patch can or can't handle an unreduced logic pattern, then you have to add extra uses of the intermediate values to prevent the other transforms from altering the instructions in the tests.

[ChuanqiXu]

Address comments.

[ChuanqiXu]

llvm/lib/Analysis/ValueTracking.cpp

290 ↗

(On Diff #406320)

Oh yes. Great Catcha.

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

This test does not add any value to the previous test. Let's try to simplify things.

Do you mean the *_thwart tests is meaningless? Or the current test doesn't add value with the pre-committed test?

> Create tests that correspond to those patterns (including using the same value names as in the test comments):

I think we have done this in the patch. Do you feel not good about the name? (Use no_common_bits_and_nor instead of src)

You can vary the types while checking the commutes, so some of the tests can use vectors (with or without an undef in the 'not' constant).

Yeah, we made this too. Do you say it would be better if every test has a vector version (and corresponding undef version)?

I'm not sure what the tests with extra 'not' instructions are showing. As we can see in the baseline CHECK lines, those are transformed before we reach the transform in this patch.

Do you talk about the case: (x & y) + (~x & ~y)? I added this from the discussion in: https://github.com/llvm/llvm-project/issues/53357. It said the form could be converted correctly after we finish the patch. Do you think the test is redundant?

[spatel]

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

I think this particular test is redundant, but we do need some "thwart" tests too. It's possible that all of the interesting patterns are covered by the tests right now, but it is difficult for me to see it. We do not need to repeat everything with vectors or vector+undef. We can reduce to the essential 4 commuted patterns and vary the types within those. That would be the most efficient set (4) of tests.

It's not necessary to include the (x & y) + (~x & ~y) patterns in this patch. We will reduce those to the minimum code independently using DeMorgan transforms.

If we want to show a limitation of this patch (when the intermediate 'not' values have extra uses), then it is fine to include more tests, but they will not be changed with this patch unless I did not understand correctly.

[ChuanqiXu]

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

Got it. Thanks. The last question is what's the reason that you think the *_thwart tests redundant. After comparing with existing example, I found a possible reason might be that I thwarted more value. Should I thwart %x only instead of thwarting both %x and %y?
Or what's the particular reason?

[spatel]

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

The baseline CHECK lines show that the pattern is identical with or without the extra instructions on this pair of tests ("src" and "src_thwart").

In fact, none of the thwart variations makes any difference on these examples. Sorry that I didn't notice this sooner, but we can not test this pattern within instcombine:

~(x | y) + (x & y)

That's because:
https://github.com/llvm/llvm-project/blob/d224be3b999afb7c4daa9c0ca807dea8123a7593/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h#L127

InstCombine will always commute the 'not' operation to be operand 1 (right-hand-side) because the other operation is an "and". You can see this in "src5".

ValueTracking may be called from other passes, so we probably want to keep the code as-is, but you can not test the variation where 'not' is operand 0 from within instcombine (it's fine to include a test to make sure that doesn't change in the future).

[ChuanqiXu]

• Remove *_thwart test. It is meaningless.
• Remove test for (x & y) + (~x & ~y)
• Add unitest for HaveNoCommonBitSet to test (X & Y) and ~(X | Y) in either order.

[ChuanqiXu]

llvm/test/Transforms/InstCombine/pr53357.ll

19–20

Thanks! I removed the *_thward tests since it looks meaningless. And I added unittest for HaveNoCommonBitSet to test ~(X | Y) and (X & Y) so that we could test it in either order.

[spatel]

llvm/unittests/Analysis/ValueTrackingTest.cpp

1760 ↗

(On Diff #408331)

Should %Add2 use %LHS2 and %RHS2? I don't think it changes anything for the EXPECT lines below, but it is confusing. Could remove all of the add instructions completely?

1780 ↗

(On Diff #408331)

Typo: "vector"

[ChuanqiXu]

Address comments.

[ChuanqiXu]

llvm/unittests/Analysis/ValueTrackingTest.cpp

1760 ↗

(On Diff #408331)

Thanks. It looks odd to me if the value is not used... but fine it is test case after all.

[spatel]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp

Instruction *InstCombinerImpl::visitAdd(BinaryOperator &I) {
   // (A + 1) + ~B --> A - B
   // ~B + (A + 1) --> A - B
   // (~B + A) + 1 --> A - B
   // (A + ~B) + 1 --> A - B
   if (match(&I, m_c_BinOp(m_Add(m_Value(A), m_One()), m_Not(m_Value(B)))) ||
       match(&I, m_BinOp(m_c_Add(m_Not(m_Value(B)), m_Value(A)), m_One())))
     return BinaryOperator::CreateSub(A, B);
 
+  // (A & B) + ~(A | B) --> ~(A ^ B)
+  if (match(&I, m_c_BinOp(m_And(m_Value(A), m_Value(B)),
+                          m_Not(m_Or(m_Value(A), m_Value(B))))))
+    return BinaryOperator::CreateNot(Builder.CreateXor(A, B));
+
   // (A + RHS) + RHS --> A + (RHS << 1)
   if (match(LHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(RHS)))))
     return BinaryOperator::CreateAdd(A, Builder.CreateShl(RHS, 1, "reass.add"));
 
   // LHS + (A + LHS) --> A + (LHS << 1)
   if (match(RHS, m_OneUse(m_c_Add(m_Value(A), m_Specific(LHS)))))
     return BinaryOperator::CreateAdd(A, Builder.CreateShl(LHS, 1, "reass.add"));
 

llvm/test/Transforms/InstCombine/pr53357.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; Test for (x & y) + ~(x | y) -> ~(x ^ y)
+; RUN: opt < %s -instcombine -S | FileCheck %s
+
+; (x & y) + ~(x | y)
+define i32 @src(i32 %0, i32 %1) {
+; CHECK-LABEL: @src(
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], -1
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = and i32 %1, %0
+  %4 = or i32 %1, %0
+  %5 = xor i32 %4, -1
+  %6 = add i32 %3, %5
+  ret i32 %6
+}
+
+; (x & y) + (~x & ~y)
+define i32 @src2(i32 %0, i32 %1) {
+; CHECK-LABEL: @src2(
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], -1
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = and i32 %1, %0
+  %4 = xor i32 %0, -1
+  %5 = xor i32 %1, -1
+  %6 = and i32 %4, %5
+  %7 = add i32 %3, %6
+  ret i32 %7
+}
+
+; ~(x | y) + (x & y)
+define i32 @src3(i32 %0, i32 %1) {
+; CHECK-LABEL: @src3(
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP1:%.*]], [[TMP0:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], -1
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = or i32 %1, %0
+  %4 = xor i32 %3, -1
+  %5 = and i32 %1, %0
+  %6 = add i32 %4, %5
+  ret i32 %6
+}
+
+; (x & y) + (~x & ~y)
+define i32 @src4(i32 %0, i32 %1) {
+; CHECK-LABEL: @src4(
+; CHECK-NEXT:    [[TMP3:%.*]] = xor i32 [[TMP0:%.*]], [[TMP1:%.*]]
+; CHECK-NEXT:    [[TMP4:%.*]] = xor i32 [[TMP3]], -1
+; CHECK-NEXT:    ret i32 [[TMP4]]
+;
+  %3 = xor i32 %0, -1
+  %4 = xor i32 %1, -1
+  %5 = and i32 %3, %4
+  %6 = and i32 %1, %0
+  %7 = add i32 %5, %6
+  ret i32 %7
+}