[InstSimplify] Fold A|B | (A^B) --> A|B

[MehrHeidar]

Summary

This patch adds the following fold opportunity:
A|B | (A^B) --> A|B

that is reported here : https://bugs.llvm.org/show_bug.cgi?id=52479

https://alive2.llvm.org/ce/z/33-My-

Test cases with base results are added in D113860

[foad]

This needs some lit tests.

llvm/lib/Analysis/InstructionSimplify.cpp

2270

Just curious: don't we have matchers that will automatically match both the swapped and non-swapped forms of a commutative op?

[MehrHeidar]

Replace m_Xor with m_c_Xor

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2270

I think there are matchers which can match both swapped operands of a commutive operands, I assume the c letter in m_c_Xor and m_c_Or for instance is standing for commutive. However, here I needed to match the operands of outer or instruction. So, I needed the commuted version as well. I am not sure, if there is any other way of doing that, because in all other folding cases implemented InstSimplify, the commuted version is added.

Also, I have added the lit test cases here D113860, to pre-commit and rebase this patch so we can show the changes.

Thanks for your comment.

[foad]

llvm/lib/Analysis/InstructionSimplify.cpp

2270

Sorry I had not noticed that you were already using m_c_Or in the first version of the patch. I think that is fine, and there is probably no need to use m_c_Xor as well?

[MehrHeidar]

Rebasing after test cases are added

[rampitec]

llvm/lib/Analysis/InstructionSimplify.cpp

2270

There is no need to use commuted matcher for the first pattern, it will match anyway.

2277

Same here, you can use just m_Xor.

[MehrHeidar]

Revert m_c_Xor to m_Xor

[MehrHeidar]

llvm/lib/Analysis/InstructionSimplify.cpp

2270

Thanks for your suggestion, right. I replaced it with m_Xor

[MehrHeidar]

Do you think the patch looks good now? @rampitec @foad
Thanks

[rampitec]

llvm/test/Transforms/InstSimplify/or.ll

456

I think you need 2 more tests with commuted 'or' operands to cover 2 m_c_Or patterns.

[MehrHeidar]

Add two more test cases for commuted or

[MehrHeidar]

llvm/test/Transforms/InstSimplify/or.ll

456

I added two more test cases as per your suggestion.
Thanks

[rampitec]

LGTM. Do you need help to push this?

[MehrHeidar]

In D113861#3132531, @rampitec wrote:

LGTM. Do you need help to push this?

Yes, I don't have commit access yet. If it's possible, can you please commit it?

Mehrnoosh Heidarpour
email: [e-mail]

[MehrHeidar]

@rampitec I think you committed this patch with your name and not mine!
I wanted you to only commit it on behalf of me. Right now, it's your patch in the repository!

[rampitec]

In D113861#3133059, @MehrHeidar wrote:

@rampitec I think you committed this patch with your name and not mine!
I wanted you to only commit it on behalf of me. Right now, it's your patch in the repository!

That's what is there: (authored by MehrHeidar, committed by rampitec): https://reviews.llvm.org/rG193c40e9667ca2b173232b393fc72ea9e4944aa3

[MehrHeidar]

In D113861#3133065, @rampitec wrote:

In D113861#3133059, @MehrHeidar wrote:

@rampitec I think you committed this patch with your name and not mine!
I wanted you to only commit it on behalf of me. Right now, it's your patch in the repository!

That's what is there: (authored by MehrHeidar, committed by rampitec): https://reviews.llvm.org/rG193c40e9667ca2b173232b393fc72ea9e4944aa3

True, that's what is there. It's under your name and not mine anymore!
Although, it was authored by me, I am only at the last line of commit message. You have not used my email address and used your own, this is your patch now.

[rampitec]

In D113861#3133079, @MehrHeidar wrote:

In D113861#3133065, @rampitec wrote:

In D113861#3133059, @MehrHeidar wrote:

@rampitec I think you committed this patch with your name and not mine!
I wanted you to only commit it on behalf of me. Right now, it's your patch in the repository!

That's what is there: (authored by MehrHeidar, committed by rampitec): https://reviews.llvm.org/rG193c40e9667ca2b173232b393fc72ea9e4944aa3

True, that's what is there. It's under your name and not mine anymore!
Although, it was authored by me, I am only at the last line of commit message. You have not used my email address and used your own, this is your patch now.

In D113861#3133079, @MehrHeidar wrote:

In D113861#3133065, @rampitec wrote:

In D113861#3133059, @MehrHeidar wrote:

@rampitec I think you committed this patch with your name and not mine!
I wanted you to only commit it on behalf of me. Right now, it's your patch in the repository!

That's what is there: (authored by MehrHeidar, committed by rampitec): https://reviews.llvm.org/rG193c40e9667ca2b173232b393fc72ea9e4944aa3

True, that's what is there. It's under your name and not mine anymore!
Although, it was authored by me, I am only at the last line of commit message. You have not used my email address and used your own, this is your patch now.

I have to admit I have no idea how to push from my account and use a different name.

[MehrHeidar]

@rampitec That was not fair, but Sometimes it happens, I think you made a mistake.

[MehrHeidar]

@rampitec Can you revert it?

[rampitec]

In D113861#3133099, @MehrHeidar wrote:

@rampitec Can you revert it?

Sure, if you so wish.

[MehrHeidar]

In D113861#3133100, @rampitec wrote:

In D113861#3133099, @MehrHeidar wrote:

@rampitec Can you revert it?

Sure, if you so wish.

Yes please. Thanks, I can ask another one to commit, maybe they know the trick to use my email address.

[aaronpuchert]

@rampitec, use git commit --author="Mehrnoosh Heidarpour <[e-mail]>". If you're --amending you might also need --reset-author.

In D113861#3133079, @MehrHeidar wrote:

Although, it was authored by me, I am only at the last line of commit message. You have not used my email address and used your own, this is your patch now.

When LLVM was still in SVN it was impossible to commit under a different name, so it's actually quite common to have the actual author named only in the message.

[MehrHeidar]

In D113861#3133150, @aaronpuchert wrote:

@rampitec, use git commit --author="Mehrnoosh Heidarpour <[e-mail]>". If you're --amending you might also need --reset-author.

In D113861#3133079, @MehrHeidar wrote:

Although, it was authored by me, I am only at the last line of commit message. You have not used my email address and used your own, this is your patch now.

When LLVM was still in SVN it was impossible to commit under a different name, so it's actually quite common to have the actual author named only in the message.

Thank you, I didn't know it will be reopened, I abandoned the other patch.

[rampitec]

In D113861#3133150, @aaronpuchert wrote:

@rampitec, use git commit --author="Mehrnoosh Heidarpour <[e-mail]>". If you're --amending you might also need --reset-author.

Thanks, good to know!

llvm/lib/Analysis/InstructionSimplify.cpp

static Value *SimplifyOrInst(Value *Op0, Value *Op1, const SimplifyQuery &Q,
   // (~A ^ B) | (B & A) -> (~A ^ B)
   // (B ^ ~A) | (A & B) -> (B ^ ~A)
   // (B ^ ~A) | (B & A) -> (B ^ ~A)
   if (match(Op1, m_And(m_Value(A), m_Value(B))) &&
       (match(Op0, m_c_Xor(m_Specific(A), m_Not(m_Specific(B)))) ||
        match(Op0, m_c_Xor(m_Not(m_Specific(A)), m_Specific(B)))))
     return Op0;
 
+  // (A | B) | (A ^ B) --> A | B
+  // (B | A) | (A ^ B) --> B | A
+  if (match(Op1, m_Xor(m_Value(A), m_Value(B))) &&
+      match(Op0, m_c_Or(m_Specific(A), m_Specific(B))))
+    return Op0;
+
+  // Commute the outer 'or' operands.
+  // (A ^ B) | (A | B) --> A | B
+  // (A ^ B) | (B | A) --> B | A
+  if (match(Op0, m_Xor(m_Value(A), m_Value(B))) &&
+      match(Op1, m_c_Or(m_Specific(A), m_Specific(B))))
+    return Op1;
+
   // (~A & B) | ~(A | B) --> ~A
   // (~A & B) | ~(B | A) --> ~A
   // (B & ~A) | ~(A | B) --> ~A
   // (B & ~A) | ~(B | A) --> ~A
   if (match(Op0, m_c_And(m_CombineAnd(m_Value(NotA), m_Not(m_Value(A))),
                          m_Value(B))) &&
       match(Op1, m_Not(m_c_Or(m_Specific(A), m_Specific(B)))))
     return NotA;

llvm/test/Transforms/InstSimplify/or.ll

;
   ret i32 %i5
 }
 
 ; (A | B) | (A ^ B) --> A | B
 
 define i69 @or_or_xor(i69 %A, i69 %B) {
 ; CHECK-LABEL: @or_or_xor(
 ; CHECK-NEXT:    [[I1:%.*]] = or i69 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[I2:%.*]] = xor i69 [[A]], [[B]]
-; CHECK-NEXT:    [[I3:%.*]] = or i69 [[I1]], [[I2]]
-; CHECK-NEXT:    ret i69 [[I3]]
+; CHECK-NEXT:    ret i69 [[I1]]
 ;
   %i1 = or i69 %A, %B
   %i2 = xor i69 %A, %B
   %i3 = or i69 %i1, %i2
   ret i69 %i3
 }
 
+; (B | A) | (A ^ B) --> B | A
+
+define i8 @or_or_xor_inner_or_commuted(i8 %A, i8 %B) {
+; CHECK-LABEL: @or_or_xor_inner_or_commuted(
+; CHECK-NEXT:    [[I1:%.*]] = or i8 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i8 [[I1]]
+;
+  %i1 = or i8 %B, %A
+  %i2 = xor i8 %A, %B
+  %i3 = or i8 %i1, %i2
+  ret i8 %i3
+}
+
+; (A ^ B) | (A | B) --> A | B
+
 define <4 x i4> @or_or_xor_commuted(<4 x i4> %A, <4 x i4> %B) {
 ; CHECK-LABEL: @or_or_xor_commuted(
 ; CHECK-NEXT:    [[I1:%.*]] = or <4 x i4> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[I2:%.*]] = xor <4 x i4> [[A]], [[B]]
-; CHECK-NEXT:    [[I3:%.*]] = or <4 x i4> [[I2]], [[I1]]
-; CHECK-NEXT:    ret <4 x i4> [[I3]]
+; CHECK-NEXT:    ret <4 x i4> [[I1]]
 ;
   %i1 = or <4 x i4> %A, %B
   %i2 = xor <4 x i4> %A, %B
   %i3 = or <4 x i4> %i2, %i1
   ret <4 x i4> %i3
 }
 
+; (A ^ B) | (B | A) --> B | A
+
+define i4 @or_or_xor_inner_or_outer_or_commuted(i4 %A, i4 %B) {
+; CHECK-LABEL: @or_or_xor_inner_or_outer_or_commuted(
+; CHECK-NEXT:    [[I1:%.*]] = or i4 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    ret i4 [[I1]]
+;
+  %i1 = or i4 %B, %A
+  %i2 = xor i4 %A, %B
+  %i3 = or i4 %i2, %i1
+  ret i4 %i3
+}
+
 define i32 @shifted_all_ones(i32 %shamt) {
 ; CHECK-LABEL: @shifted_all_ones(
 ; CHECK-NEXT:    ret i32 -1
 ;
   %r = lshr i32 -1, %shamt
   %s = sub i32 32, %shamt
   %l = shl i32 -1, %s
   %o = or i32 %r, %l