This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] transform pattern "(~A & B) ^ A -> (A | B)" added
ClosedPublic

Authored by spatel on Aug 22 2020, 4:45 AM.

Details

Summary

This patch implements transform for pattern "(~A & B) ^ A -> (A | B)".

And this pattern is already implemented in gcc.

Diff Detail

Event Timeline

Jac1494 created this revision.Aug 22 2020, 4:45 AM
Jac1494 requested review of this revision.Aug 22 2020, 4:45 AM
xbolva00 added inline comments.
llvm/test/Transforms/InstCombine/xor-or.ll
5

define i32 @test2(i32 %0, i32 %1) {

%3 = xor i32 %0, -1
%4 = and i32 %1, %3
%5 = xor i32 %4, %0
ret i32 %5

}

define i32 @test3(i32 %0, i32 %1) {

%3 = xor i32 %0, -1
%4 = and i32 %3, %1
%5 = xor i32 %0, %4
ret i32 %5

}

5

Remove dso_local and "local_unnamed_addr #0"

Jac1494 updated this revision to Diff 287184.Aug 22 2020, 7:05 AM

Addressed @xbolva00 review comments. Thanks

Jac1494 updated this revision to Diff 287465.Aug 24 2020, 12:22 PM

Added more test cases.

The tests should be pre-committed with current CHECK lines (ie, without this patch), so we just see the diffs - and can confirm that the tests actually represent the patterns shown in the test comments.

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

What about the case where the and is Op1?

llvm/test/Transforms/InstCombine/xor-or.ll
21

This test doesn't match the comment.

You need something like this:

define i32 @test2(i32 %p, i32 %y) {
  %x = add i32 %p, 42 ; thwart complexity-based canonicalization
  %n = xor i32 %x, -1
  %a = and i32 %n, %y
  %r = xor i32 %x, %a
  ret i32 %r
}
Jac1494 updated this revision to Diff 288321.Aug 27 2020, 7:21 AM

Added new pattern "A ^ (~A & B) --> (A | B)" .

The tests should be pre-committed with current CHECK lines (ie, without this patch), so we just see the diffs - and can confirm that the tests actually represent the patterns shown in the test comments.

I have created IR and assembly files like below (without this patch), And I am not getting "%x = add i32 %p, 42 ; thwart complexity-based canonicalization"
But it is there in assembly.

$ cat test.c

int f(int A,int B)
{
    return(A ^ (~A & B));
}

$ clang test.c -S -O1 -emit-llvm
$ cat test.ll
...
...
define dso_local i32 @f(i32 %0, i32 %1) local_unnamed_addr #0 {
  %3 = xor i32 %0, -1
  %4 = and i32 %3, %1
  %5 = xor i32 %4, %0
  ret i32 %5
}
...
...
$ clang test.c -S -O1
$ cat test.s
...
f:                                      # @f
        .cfi_startproc
# %bb.0:
        movl    %edi, %eax
        notl    %eax
        andl    %esi, %eax
        xorl    %edi, %eax
        retq
.Lfunc_end0:
...

The tests should be pre-committed with current CHECK lines (ie, without this patch), so we just see the diffs - and can confirm that the tests actually represent the patterns shown in the test comments.

I have created IR and assembly files like below (without this patch), And I am not getting "%x = add i32 %p, 42 ; thwart complexity-based canonicalization"
But it is there in assembly.

Assembly is irrelevant. This is an IR to IR patch.
You are proposing to transform 4 commuted variations of a pattern, but your tests do not provide coverage for those variants. My test suggestion would hopefully provide that coverage.
This might be clearer if you create the tests before this code patch and step through the transforms in a debugger. Look for InstCombinerImpl::SimplifyAssociativeOrCommutative() and getComplexity().

You are proposing to transform 4 commuted variations of a pattern, but your tests do not provide coverage for those variants. My test suggestion would hopefully provide that coverage.
This might be clearer if you create the tests before this code patch and step through the transforms in a debugger. Look for InstCombinerImpl::SimplifyAssociativeOrCommutative() and getComplexity().

@spatel ,Thank you so much for such informative reply. Now anything is pending in review which need to be update?

xbolva00 added inline comments.Aug 29 2020, 7:45 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
3361

Avoid this.

Use

if (match(&I, m_c_Xor(......)

above.

Jac1494 updated this revision to Diff 288779.Aug 29 2020, 8:55 AM

Addressed @xbolva00 review comments.

xbolva00 added inline comments.Aug 29 2020, 9:01 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
3361

Now you can remove this fold, since previous check ^ handles commutation.

Jac1494 updated this revision to Diff 288782.Aug 29 2020, 9:22 AM

Removed unnecessary code.

No furher comments from me. If possible, commit new tests and rebase this patch.

Wait for @spatel too.

llvm/test/Transforms/InstCombine/xor-or.ll
21

Not done?

You are proposing to transform 4 commuted variations of a pattern, but your tests do not provide coverage for those variants. My test suggestion would hopefully provide that coverage.
This might be clearer if you create the tests before this code patch and step through the transforms in a debugger. Look for InstCombinerImpl::SimplifyAssociativeOrCommutative() and getComplexity().

@spatel ,Thank you so much for such informative reply. Now anything is pending in review which need to be update?

I don't see any changes to the tests from the earlier draft of the patch. That is, test1 and test2 are identical unless I'm not seeing correctly? Please open a separate review to add only the test file, so we can work through that independently of the code change.

You might consider adding tests to an existing file like llvm/test/Transforms/InstCombine/xor.ll instead of creating a new file for just ~4 tests. If my earlier comment about the tests did not make sense, please grep for "thwart" in this test directory to see examples.

If my earlier comment about the tests did not make sense, please grep for "thwart" in this test directory to see examples.

A bit of clarification needed(I'm still new to this) @spatel .
Can you please explain what is purpose of this line ?? And is this 42 value conveying something special to codegen pipeline ??

x = add i32 %p, 42 ; thwart complexity-based canonicalization

And How to create this. ?? Because I have tried to create IR(test case) with optimization without this patch but i am not getting this line.

spatel added a comment.Sep 2 2020, 1:36 PM

If my earlier comment about the tests did not make sense, please grep for "thwart" in this test directory to see examples.

A bit of clarification needed(I'm still new to this) @spatel .
Can you please explain what is purpose of this line ?? And is this 42 value conveying something special to codegen pipeline ??

Sure - "42" represents an arbitrary value. I'm not sure if this was the original joke, but see - https://en.wikipedia.org/wiki/Phrases_from_The_Hitchhiker%27s_Guide_to_the_Galaxy#Answer_to_the_Ultimate_Question_of_Life,_the_Universe,_and_Everything_(42)

x = add i32 %p, 42 ; thwart complexity-based canonicalization

And How to create this. ?? Because I have tried to create IR(test case) with optimization without this patch but i am not getting this line.

Instcombine is changing the IR before it reaches your patched code. I suggest again to step through your current "test6" in the debugger and/or run "opt -debug" to see what is happening.

The "thwart" instruction is creating an xor that has binops as both operands. That is required to prevent instcombine from rearranging the operands before it reaches your code.

Jac1494 updated this revision to Diff 290305.Sep 7 2020, 9:36 AM

@spatel test cases are updated as per your review comments. Thanks for this.
And these test cases were failing without this patch. So it means that patch is doing correct transformations.

IR Without my patch(for test52):-

define i32 @test52(i32 %0, i32 %1) {
  %3 = xor i32 %0, -1
  %4 = and i32 %3, %1
  %5 = xor i32 %4, %0
  ret i32 %5
}

IR after my patch(Transformation applied):-

define i32 @test52(i32 %0, i32 %1) {
  %3 = or i32 %1, %0
  ret i32 %3
}
spatel added a comment.Sep 8 2020, 6:55 AM

I committed the baseline tests, so we can see diffs. Please rebase.
Try this experiment to see if your tests provide the coverage that we expect:

  1. Replace the "m_c_XXX" matchers with the non-commute equivalent.
  2. Exactly 1 test should be modified.
  3. Add back only 1 of the commutative matchers.
  4. Exactly 2 tests should be modified.
  5. Invert the commutativity of the matchers (so the opposite matcher is now commutative).
  6. Exactly 2 tests should be modified.
  7. Make both matchers commutative.
  8. All 4 tests should be modified.

Please update the tests and/or test comments if that is not working.

Jac1494 updated this revision to Diff 291045.Sep 10 2020, 11:57 AM
Jac1494 retitled this revision from InstCombine transform pattern "(~A & B) ^ A -> (A | B)" added to [InstCombine] transform pattern "(~A & B) ^ A -> (A | B)" added.

Test cases are tested and updated.

This comment was removed by xbolva00.
spatel requested changes to this revision.Sep 10 2020, 1:16 PM
spatel added inline comments.
llvm/test/Transforms/InstCombine/xor.ll
1193 ↗(On Diff #291045)

This test doesn't exercise anything differently than "test52"; it just reversed the value names.

This revision now requires changes to proceed.Sep 10 2020, 1:16 PM
xbolva00 added inline comments.Sep 10 2020, 1:19 PM
llvm/test/Transforms/InstCombine/xor.ll
1179 ↗(On Diff #291045)

Any vector test?

Jac1494 updated this revision to Diff 291230.Sep 11 2020, 8:52 AM

Addressed the review comments of @spatel and @xbolva00 .

Try this experiment to see if your tests provide the coverage that we expect:

  1. Replace the "m_c_XXX" matchers with the non-commute equivalent.
  2. Exactly 1 test should be modified.
  3. Add back only 1 of the commutative matchers.
  4. Exactly 2 tests should be modified.
  5. Invert the commutativity of the matchers (so the opposite matcher is now commutative).
  6. Exactly 2 tests should be modified.
  7. Make both matchers commutative.
  8. All 4 tests should be modified.

Did you try this with the tests as shown in this draft of the patch?

Try this experiment to see if your tests provide the coverage that we expect:

  1. Replace the "m_c_XXX" matchers with the non-commute equivalent.
  2. Exactly 1 test should be modified.
  3. Add back only 1 of the commutative matchers.
  4. Exactly 2 tests should be modified.
  5. Invert the commutativity of the matchers (so the opposite matcher is now commutative).
  6. Exactly 2 tests should be modified.
  7. Make both matchers commutative.
  8. All 4 tests should be modified.

Did you try this with the tests as shown in this draft of the patch?

Yes, @spatel I have tried this cases with tests of this patch.

Try this experiment to see if your tests provide the coverage that we expect:

  1. Replace the "m_c_XXX" matchers with the non-commute equivalent.
  2. Exactly 1 test should be modified.
  3. Add back only 1 of the commutative matchers.
  4. Exactly 2 tests should be modified.
  5. Invert the commutativity of the matchers (so the opposite matcher is now commutative).
  6. Exactly 2 tests should be modified.
  7. Make both matchers commutative.
  8. All 4 tests should be modified.

Did you try this with the tests as shown in this draft of the patch?

Yes, @spatel I have tried this cases with tests of this patch.

Then I think something is wrong with your build environment. If I remove the commutative matchers, I get 0 test diffs. This makes sense given that test53 is still identical to test52 in terms of commutative matching (the only differences now are the value types).

spatel added inline comments.Sep 11 2020, 9:37 AM
llvm/test/Transforms/InstCombine/xor.ll
1237 ↗(On Diff #291230)

The canonicalized form of the 'and' is different than how it was written. This test is not checking the pattern that you intended it to check.

Try this experiment to see if your tests provide the coverage that we expect:

  1. Replace the "m_c_XXX" matchers with the non-commute equivalent.
  2. Exactly 1 test should be modified.
  3. Add back only 1 of the commutative matchers.
  4. Exactly 2 tests should be modified.
  5. Invert the commutativity of the matchers (so the opposite matcher is now commutative).
  6. Exactly 2 tests should be modified.
  7. Make both matchers commutative.
  8. All 4 tests should be modified.

Did you try this with the tests as shown in this draft of the patch?

Yes, @spatel I have tried this cases with tests of this patch.

Then I think something is wrong with your build environment. If I remove the commutative matchers, I get 0 test diffs.

@spatel it is also same for me. If I remove both the commutative matchers than I also get 0 test diffs.(change x_c_Xor with x_Xor and x_c_And with x_And)

This makes sense given that test53 is still identical to test52 in terms of commutative matching (the only differences now are the value types).

Added test53 to cover vector test. I will update/remove the test53.

Jac1494 updated this revision to Diff 291286.Sep 11 2020, 11:33 AM

test53 and test55 has been removed.

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

@spatel, apologies for the confusion created due to multiple revisions.

Let's consider the initial pattern and associated commutative version of this.

initial pattern:-
(~A & B) ^ A -> (A | B) 

And 8 possible commutative version of this.
1) (~A & B) ^ A -> (A | B) 
2) (~B & A) ^ B -> (A | B)
3) (B & ~A) ^ A -> (A | B)  --> identical to 1)
4) A ^ (~A & B) -> (A | B)  --> identical to 1)
5) A ^ (B & ~A) -> (A | B)  --> identical to 1)
6) (A & ~B) ^ B -> (A | B)  --> identical to 2)
7) B ^ (~B & A) -> (A | B)  --> identical to 2)
8) B ^ (A & ~B) -> (A | B)  --> identical to 2)

As you may notice that all these patterns (IR) are reducing to 2 unique patterns (pattern 1 and pattern 2).
So pattern 1 and 2 are sufficient for the coverage of all commutative variations of the primary pattern.
Does this matches with you understandings ??

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

@spatel, apologies for the confusion created due to multiple revisions.

Let's consider the initial pattern and associated commutative version of this.

initial pattern:-
(~A & B) ^ A -> (A | B) 

And 8 possible commutative version of this.
1) (~A & B) ^ A -> (A | B) 
2) (~B & A) ^ B -> (A | B)
3) (B & ~A) ^ A -> (A | B)  --> identical to 1)
4) A ^ (~A & B) -> (A | B)  --> identical to 1)
5) A ^ (B & ~A) -> (A | B)  --> identical to 1)
6) (A & ~B) ^ B -> (A | B)  --> identical to 2)
7) B ^ (~B & A) -> (A | B)  --> identical to 2)
8) B ^ (A & ~B) -> (A | B)  --> identical to 2)

As you may notice that all these patterns (IR) are reducing to 2 unique patterns (pattern 1 and pattern 2).
So pattern 1 and 2 are sufficient for the coverage of all commutative variations of the primary pattern.

How so?
If you only have a test for pattern 1 and pattern 2, how do you know that the commutative variants are handled?

Does this matches with you understandings ??

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

@spatel, apologies for the confusion created due to multiple revisions.

Let's consider the initial pattern and associated commutative version of this.

initial pattern:-
(~A & B) ^ A -> (A | B) 

And 8 possible commutative version of this.
1) (~A & B) ^ A -> (A | B) 
2) (~B & A) ^ B -> (A | B)
3) (B & ~A) ^ A -> (A | B)  --> identical to 1)
4) A ^ (~A & B) -> (A | B)  --> identical to 1)
5) A ^ (B & ~A) -> (A | B)  --> identical to 1)
6) (A & ~B) ^ B -> (A | B)  --> identical to 2)
7) B ^ (~B & A) -> (A | B)  --> identical to 2)
8) B ^ (A & ~B) -> (A | B)  --> identical to 2)

As you may notice that all these patterns (IR) are reducing to 2 unique patterns (pattern 1 and pattern 2).
So pattern 1 and 2 are sufficient for the coverage of all commutative variations of the primary pattern.

How so?
If you only have a test for pattern 1 and pattern 2, how do you know that the commutative variants are handled?

Does this matches with you understandings ??

@lebedev.ri , I have manually tested and verified.

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

@spatel, apologies for the confusion created due to multiple revisions.

Let's consider the initial pattern and associated commutative version of this.

initial pattern:-
(~A & B) ^ A -> (A | B) 

And 8 possible commutative version of this.
1) (~A & B) ^ A -> (A | B) 
2) (~B & A) ^ B -> (A | B)
3) (B & ~A) ^ A -> (A | B)  --> identical to 1)
4) A ^ (~A & B) -> (A | B)  --> identical to 1)
5) A ^ (B & ~A) -> (A | B)  --> identical to 1)
6) (A & ~B) ^ B -> (A | B)  --> identical to 2)
7) B ^ (~B & A) -> (A | B)  --> identical to 2)
8) B ^ (A & ~B) -> (A | B)  --> identical to 2)

As you may notice that all these patterns (IR) are reducing to 2 unique patterns (pattern 1 and pattern 2).
So pattern 1 and 2 are sufficient for the coverage of all commutative variations of the primary pattern.
Does this matches with you understandings ??

No. First, there are not 8 unique patterns. There are 4. For the sake of consistency with the code that you have proposed, you can always think of "A" as the operand with a not. Renaming that to "B" or "Foo" or anything else does not change the logic.
Second, I don't think you understand how commutative canonicalization works - you should put a breakpoint in here and step through in a debugger:
https://github.com/llvm/llvm-project/blob/4452cc4086aca1a424b2cd40da9fa120add522e7/llvm/include/llvm/Transforms/InstCombine/InstCombiner.h#L126
Third, you ignored my earlier suggestion to open a review to add/modify the tests alone. Please do that now, so we can reach a conclusion sooner.

test53 and test55 has been removed.

We are going in circles. I'll give this 1 more try, and if it still doesn't make sense, then maybe another reviewer can better communicate what we expect for the tests:

  1. There are 4 commutative patterns variations in the code.
  2. Each one of those patterns should have a test (we should have at least 4 tests).
  3. Each test corresponds to exactly one of the commutative patterns.
  4. Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
  5. The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.

@spatel, apologies for the confusion created due to multiple revisions.

Let's consider the initial pattern and associated commutative version of this.

initial pattern:-
(~A & B) ^ A -> (A | B) 

And 8 possible commutative version of this.
1) (~A & B) ^ A -> (A | B) 
2) (~B & A) ^ B -> (A | B)
3) (B & ~A) ^ A -> (A | B)  --> identical to 1)
4) A ^ (~A & B) -> (A | B)  --> identical to 1)
5) A ^ (B & ~A) -> (A | B)  --> identical to 1)
6) (A & ~B) ^ B -> (A | B)  --> identical to 2)
7) B ^ (~B & A) -> (A | B)  --> identical to 2)
8) B ^ (A & ~B) -> (A | B)  --> identical to 2)

As you may notice that all these patterns (IR) are reducing to 2 unique patterns (pattern 1 and pattern 2).
So pattern 1 and 2 are sufficient for the coverage of all commutative variations of the primary pattern.

How so?
If you only have a test for pattern 1 and pattern 2, how do you know that the commutative variants are handled?

Does this matches with you understandings ??

@lebedev.ri , I have manually tested and verified.

And do you plan on "manually testing and re-verifying" that on each commit to LLVM as a whole made by everyone for the forseeable future?

silvas resigned from this revision.Sep 22 2020, 7:25 PM
Jac1494 updated this revision to Diff 295229.Sep 30 2020, 3:31 AM

Separate review created for test cases. (https://reviews.llvm.org/D88551)

dexonsmith resigned from this revision.Oct 6 2020, 3:19 PM
spatel commandeered this revision.Oct 15 2020, 11:55 AM
spatel edited reviewers, added: Jac1494; removed: spatel.

Commandeering to update.

spatel updated this revision to Diff 298433.Oct 15 2020, 11:56 AM

Rebased after adding test coverage for the 4 commuted variants.
https://alive2.llvm.org/ce/z/YopFEU

spatel marked an inline comment as done.Oct 17 2020, 6:32 AM

The tests now provide commutative coverage for the 4 variations of the pattern. If there are no other suggestions, can someone officially approve? Thanks!

lebedev.ri accepted this revision.Oct 17 2020, 6:37 AM

LGTM, thanks.

This revision is now accepted and ready to land.Oct 17 2020, 6:37 AM
This revision was automatically updated to reflect the committed changes.