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

[spatel]

Summary

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

And this pattern is already implemented in gcc.

[xbolva00]

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

4 ↗

(On Diff #287172)

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

}

4 ↗

(On Diff #287172)

Remove dso_local and "local_unnamed_addr #0"

[Jac1494]

Addressed @xbolva00 review comments. Thanks

[Jac1494]

Added more test cases.

[spatel]

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 ↗

(On Diff #287465)

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]

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

[Jac1494]

In D86395#2234640, @spatel wrote:

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:
...

[spatel]

In D86395#2242098, @Jac1494 wrote:

In D86395#2234640, @spatel wrote:

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().

[Jac1494]

In D86395#2242393, @spatel wrote:

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]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3361

Avoid this.

Use

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

above.

[Jac1494]

Addressed @xbolva00 review comments.

[xbolva00]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3361

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

[Jac1494]

Removed unnecessary code.

[xbolva00]

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 ↗

(On Diff #287465)

Not done?

[spatel]

In D86395#2246092, @Jac1494 wrote:

In D86395#2242393, @spatel wrote:

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.

[Jac1494]

In D86395#2246162, @spatel wrote:

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]

In D86395#2252636, @Jac1494 wrote:

In D86395#2246162, @spatel wrote:

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]

@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]

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]

Test cases are tested and updated.

[xbolva00]

This comment was removed by xbolva00.

[spatel]

llvm/test/Transforms/InstCombine/xor.ll

1193

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

[xbolva00]

llvm/test/Transforms/InstCombine/xor.ll

1179

Any vector test?

[Jac1494]

Addressed the review comments of @spatel and @xbolva00 .

[spatel]

In D86395#2260871, @spatel wrote:

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?

[Jac1494]

In D86395#2268096, @spatel wrote:

In D86395#2260871, @spatel wrote:

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.

[spatel]

In D86395#2268155, @Jac1494 wrote:

In D86395#2268096, @spatel wrote:

In D86395#2260871, @spatel wrote:

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]

llvm/test/Transforms/InstCombine/xor.ll

1237

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.

[Jac1494]

In D86395#2268209, @spatel wrote:

In D86395#2268155, @Jac1494 wrote:

In D86395#2268096, @spatel wrote:

In D86395#2260871, @spatel wrote:

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]

test53 and test55 has been removed.

[spatel]

In D86395#2268634, @Jac1494 wrote:

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.

[Jac1494]

In D86395#2269436, @spatel wrote:

In D86395#2268634, @Jac1494 wrote:

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 ??

[lebedev.ri]

In D86395#2274522, @Jac1494 wrote:

In D86395#2269436, @spatel wrote:

In D86395#2268634, @Jac1494 wrote:

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 ??

[Jac1494]

In D86395#2274541, @lebedev.ri wrote:

In D86395#2274522, @Jac1494 wrote:

In D86395#2269436, @spatel wrote:

In D86395#2268634, @Jac1494 wrote:

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.

[spatel]

In D86395#2274522, @Jac1494 wrote:

In D86395#2269436, @spatel wrote:

In D86395#2268634, @Jac1494 wrote:

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.

[lebedev.ri]

In D86395#2274565, @Jac1494 wrote:

In D86395#2274541, @lebedev.ri wrote:

In D86395#2274522, @Jac1494 wrote:

In D86395#2269436, @spatel wrote:

In D86395#2268634, @Jac1494 wrote:

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?

[Jac1494]

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

[spatel]

Commandeering to update.

[spatel]

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

[spatel]

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]

LGTM, thanks.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
     return BinaryOperator::CreateOr(A, B);
 
   // (A & ~B) ^ ~A -> ~(A & B)
   // (~B & A) ^ ~A -> ~(A & B)
   if (match(Op0, m_c_And(m_Value(A), m_Not(m_Value(B)))) &&
       match(Op1, m_Not(m_Specific(A))))
     return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
 
+  // (~A & B) ^ A --> A | B -- There are 4 commuted variants.
+  if (match(&I, m_c_Xor(m_c_And(m_Not(m_Value(A)), m_Value(B)), m_Deferred(A))))
+    return BinaryOperator::CreateOr(A, B);
+
   // (A | B) ^ (A | C) --> (B ^ C) & ~A -- There are 4 commuted variants.
   // TODO: Loosen one-use restriction if common operand is a constant.
   Value *D;
   if (match(Op0, m_OneUse(m_Or(m_Value(A), m_Value(B)))) &&
       match(Op1, m_OneUse(m_Or(m_Value(C), m_Value(D))))) {
     if (B == C || B == D)
       std::swap(A, B);
     if (A == C)
       std::swap(C, D);
     if (A == D) {
       Value *NotA = Builder.CreateNot(A);
       return BinaryOperator::CreateAnd(Builder.CreateXor(B, C), NotA);
     }
   }
 
   if (auto *LHS = dyn_cast<ICmpInst>(I.getOperand(0)))
     if (auto *RHS = dyn_cast<ICmpInst>(I.getOperand(1)))
       if (Value *V = foldXorOfICmps(LHS, RHS, I))
         return replaceInstUsesWith(I, V);
 
   if (Instruction *CastedXor = foldCastedBitwiseLogic(I))
     return CastedXor;
 
   // Canonicalize a shifty way to code absolute value to the common pattern.
   // There are 4 potential commuted variants. Move the 'ashr' candidate to Op1.
   // We're relying on the fact that we only do this transform when the shift has
   // exactly 2 uses and the add has exactly 1 use (otherwise, we might increase
   // instructions).

llvm/test/Transforms/InstCombine/xor.ll

;
   %r = xor i8 %a, -2
   ret i8 %r
 }
 
 ; (~A & B) ^ A --> A | B
 
 define <2 x i32> @xor_andn_commute1(<2 x i32> %a, <2 x i32> %b) {
 ; CHECK-LABEL: @xor_andn_commute1(
-; CHECK-NEXT:    [[NOTA:%.*]] = xor <2 x i32> [[A:%.*]], <i32 -1, i32 -1>
-; CHECK-NEXT:    [[R:%.*]] = and <2 x i32> [[NOTA]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i32> [[R]], [[A]]
+; CHECK-NEXT:    [[Z:%.*]] = or <2 x i32> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret <2 x i32> [[Z]]
 ;
   %nota = xor <2 x i32> %a, <i32 -1, i32 -1>
   %r = and <2 x i32> %nota, %b
   %z = xor <2 x i32> %r, %a
   ret <2 x i32> %z
 }
 
 ; (B & ~A) ^ A --> A | B
 
 define i33 @xor_andn_commute2(i33 %a, i33 %pb) {
 ; CHECK-LABEL: @xor_andn_commute2(
 ; CHECK-NEXT:    [[B:%.*]] = udiv i33 42, [[PB:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i33 [[A:%.*]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i33 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i33 [[R]], [[A]]
+; CHECK-NEXT:    [[Z:%.*]] = or i33 [[B]], [[A:%.*]]
 ; CHECK-NEXT:    ret i33 [[Z]]
 ;
   %b = udiv i33 42, %pb ; thwart complexity-based canonicalization
   %nota = xor i33 %a, -1
   %r = and i33 %b, %nota
   %z = xor i33 %r, %a
   ret i33 %z
 }
 
 ; A ^ (~A & B) --> A | B
 
 define i32 @xor_andn_commute3(i32 %pa, i32 %b) {
 ; CHECK-LABEL: @xor_andn_commute3(
 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[NOTA]], [[B:%.*]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[A]], [[R]]
+; CHECK-NEXT:    [[Z:%.*]] = or i32 [[A]], [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
   %nota = xor i32 %a, -1
   %r = and i32 %nota, %b
   %z = xor i32 %a, %r
   ret i32 %z
 }
 
 ; A ^ (B & ~A) --> A | B
 
 define i32 @xor_andn_commute4(i32 %pa, i32 %pb) {
 ; CHECK-LABEL: @xor_andn_commute4(
 ; CHECK-NEXT:    [[A:%.*]] = udiv i32 42, [[PA:%.*]]
 ; CHECK-NEXT:    [[B:%.*]] = udiv i32 42, [[PB:%.*]]
-; CHECK-NEXT:    [[NOTA:%.*]] = xor i32 [[A]], -1
-; CHECK-NEXT:    [[R:%.*]] = and i32 [[B]], [[NOTA]]
-; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[A]], [[R]]
+; CHECK-NEXT:    [[Z:%.*]] = or i32 [[A]], [[B]]
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %a = udiv i32 42, %pa ; thwart complexity-based canonicalization
   %b = udiv i32 42, %pb ; thwart complexity-based canonicalization
   %nota = xor i32 %a, -1
   %r = and i32 %b, %nota
   %z = xor i32 %a, %r
   ret i32 %z
 }