This patch implements transform for pattern "(~A & B) ^ A -> (A | B)".
And this pattern is already implemented in gcc.
Details
Details
Diff Detail
Diff Detail
Event Timeline
| 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" | |
Comment Actions
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
} | |
Comment Actions
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: ...
Comment Actions
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().
Comment Actions
@spatel ,Thank you so much for such informative reply. Now anything is pending in review which need to be update?
| llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
|---|---|---|
| 3361 | Avoid this. Use if (match(&I, m_c_Xor(......) above. | |
| llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | ||
|---|---|---|
| 3361 | Now you can remove this fold, since previous check ^ handles commutation. | |
Comment Actions
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.
Comment Actions
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.
Comment Actions
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 canonicalizationAnd 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.
Comment Actions
@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
}Comment Actions
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:
- Replace the "m_c_XXX" matchers with the non-commute equivalent.
- Exactly 1 test should be modified.
- Add back only 1 of the commutative matchers.
- Exactly 2 tests should be modified.
- Invert the commutativity of the matchers (so the opposite matcher is now commutative).
- Exactly 2 tests should be modified.
- Make both matchers commutative.
- All 4 tests should be modified.
Please update the tests and/or test comments if that is not working.
This comment was removed by xbolva00.
| 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. |
| llvm/test/Transforms/InstCombine/xor.ll | ||
|---|---|---|
| 1179 ↗ | (On Diff #291045) | Any vector test? |
Comment Actions
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).
| 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. |
Comment Actions
@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.
Comment Actions
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:
- There are 4 commutative patterns variations in the code.
- Each one of those patterns should have a test (we should have at least 4 tests).
- Each test corresponds to exactly one of the commutative patterns.
- Each test should be in canonical form without this patch (the baseline CHECK lines should correspond exactly to the IR as written).
- The 8 step check I provided earlier may be used to confirm that the tests provide the expected coverage for the code.
Comment Actions
@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 ??
Comment Actions
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 ??
Comment Actions
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.
Comment Actions
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?
Comment Actions
Rebased after adding test coverage for the 4 commuted variants.
https://alive2.llvm.org/ce/z/YopFEU
Comment Actions
The tests now provide commutative coverage for the 4 variations of the pattern. If there are no other suggestions, can someone officially approve? Thanks!
What about the case where the and is Op1?