[InstCombine] Fold (A^B)|~A-->~(A&B)

[MehrHeidar]

Summary

This patch fixes bug Failure to simplify (A^B)|~A --> ~(A&B) reported here:
https://bugs.llvm.org/show_bug.cgi?id=52478

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2676

This surprised me, but this seems to work. Note that 'not' is also an 'xor' operation.
But canonicalization rules will always put the 'not' operand on the right (operand 1). So the swap above here then guarantees that the 'not' is operand 0.

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

62

We need another test where X and Y are commuted.
We also need at least 3 tests with extra uses: (1) extra use of the 'not', (2) extra use of the regular 'xor', (3) extra uses of both of those.
The transform should be fine as long there is only one use for either of the operands because we are eliminating an instruction in this sequence.
When creating more tests, it's good to vary the data types a bit so we have better coverage. For example, have one test use vector types and another use a weird type like 'i65'.

[MehrHeidar]

Addressing review comments.

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2676

Right, that is exactly the reason that I put the code after the swap in line 2671. If it is not appropriate I can change it.

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

62

Thank you; I have added a few more tests based on your suggestion.

[MehrHeidar]

Modify name of one of the values in one of the test cases added in previous commit.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2676

I think it's ok, but it would be nice to add the explanation to the code comment. So something like this:
// ~A | (A ^ B) -> ~(A & B) -- The swap above should always make Op0 the 'not'.

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

62

Tests look good. Do you have commit access? If so, please pre-commit the tests with the baseline results, so we will show how the code changes in this patch.

[MehrHeidar]

Add a comment to clarify the Op0 in the or operation is guaranteed to be not in the foldable pattern due to the swap that is happening before.

[MehrHeidar]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2676

Thank you; I have added your suggested comment.

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

62

No, I do not have commit access; But I prepared another patch to pre-commit the tests with baseline results here: https://reviews.llvm.org/D113846

If it's possible, Can you please commit it for me?
Thank you.

[MehrHeidar]

Rebase after pre-committing the test cases with base result.

[spatel]

LGTM

Do you have enough commits/reviews now to request commit access? ( https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access )

[MehrHeidar]

In D113783#3131766, @spatel wrote:

LGTM

Do you have enough commits/reviews now to request commit access? ( https://llvm.org/docs/DeveloperPolicy.html#obtaining-commit-access )

Not yet, but I'll have soon. I guess after this one and D113861, I can request it.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
   bool SwappedForXor = false;
   if (match(Op0, m_Xor(m_Value(), m_Value()))) {
     std::swap(Op0, Op1);
     SwappedForXor = true;
   }
 
   // A | ( A ^ B) -> A |  B
   // A | (~A ^ B) -> A | ~B
   // (A & B) | (A ^ B)
+  // ~A | (A ^ B) -> ~(A & B)
+  // The swap above should always make Op0 the 'not' for the last case.
   if (match(Op1, m_Xor(m_Value(A), m_Value(B)))) {
     if (Op0 == A || Op0 == B)
       return BinaryOperator::CreateOr(A, B);
 
     if (match(Op0, m_And(m_Specific(A), m_Specific(B))) ||
         match(Op0, m_And(m_Specific(B), m_Specific(A))))
       return BinaryOperator::CreateOr(A, B);
 
+    if ((Op0->hasOneUse() || Op1->hasOneUse()) &&
+        (match(Op0, m_Not(m_Specific(A))) || match(Op0, m_Not(m_Specific(B)))))
+      return BinaryOperator::CreateNot(Builder.CreateAnd(A, B));
+
     if (Op1->hasOneUse() && match(A, m_Not(m_Specific(Op0)))) {
       Value *Not = Builder.CreateNot(B, B->getName() + ".not");
       return BinaryOperator::CreateOr(Not, Op0);
     }
     if (Op1->hasOneUse() && match(B, m_Not(m_Specific(Op0)))) {
       Value *Not = Builder.CreateNot(A, A->getName() + ".not");
       return BinaryOperator::CreateOr(Not, Op0);
     }

llvm/test/Transforms/InstCombine/and-or-icmps.ll

 define void @simplify_before_foldAndOfICmps() {
 ; CHECK-LABEL: @simplify_before_foldAndOfICmps(
 ; CHECK-NEXT:    [[A8:%.*]] = alloca i16, align 2
 ; CHECK-NEXT:    [[L7:%.*]] = load i16, i16* [[A8]], align 2
 ; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i16 [[L7]], -1
 ; CHECK-NEXT:    [[B11:%.*]] = zext i1 [[TMP1]] to i16
 ; CHECK-NEXT:    [[C10:%.*]] = icmp ugt i16 [[L7]], [[B11]]
 ; CHECK-NEXT:    [[C5:%.*]] = icmp slt i16 [[L7]], 1
-; CHECK-NEXT:    [[C11:%.*]] = icmp ne i16 [[L7]], 0
 ; CHECK-NEXT:    [[C7:%.*]] = icmp slt i16 [[L7]], 0
 ; CHECK-NEXT:    [[B15:%.*]] = xor i1 [[C7]], [[C10]]
-; CHECK-NEXT:    [[B19:%.*]] = xor i1 [[C11]], [[B15]]
+; CHECK-NEXT:    [[C6:%.*]] = xor i1 [[B15]], true
 ; CHECK-NEXT:    [[TMP2:%.*]] = and i1 [[C10]], [[C5]]
-; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[B19]]
+; CHECK-NEXT:    [[C3:%.*]] = and i1 [[TMP2]], [[C6]]
 ; CHECK-NEXT:    [[TMP3:%.*]] = xor i1 [[C10]], true
 ; CHECK-NEXT:    [[C18:%.*]] = or i1 [[C7]], [[TMP3]]
 ; CHECK-NEXT:    [[TMP4:%.*]] = sext i1 [[C3]] to i64
 ; CHECK-NEXT:    [[G26:%.*]] = getelementptr i1, i1* null, i64 [[TMP4]]
 ; CHECK-NEXT:    store i16 [[L7]], i16* undef, align 2
 ; CHECK-NEXT:    store i1 [[C18]], i1* undef, align 1
 ; CHECK-NEXT:    store i1* [[G26]], i1** undef, align 8
 ; CHECK-NEXT:    ret void

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

 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %xor = xor i32 %x, %y
   %not = xor i32 %xor, -1
   %z = or i32 %y, %not
   ret i32 %z
 }
 
 ; (X ^ Y) | ~X  --> ~(X & Y)
 
 define i32 @test5(i32 %x, i32 %y) {
 ; CHECK-LABEL: @test5(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i32 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i32 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i32 [[TMP1]], -1
 ; CHECK-NEXT:    ret i32 [[Z]]
 ;
   %xor = xor i32 %x, %y
   %notx = xor i32 %x, -1
   %z = or i32 %xor, %notx
   ret i32 %z
 }
 
 ; Commute the 'or' operands
 ; ~X | (X ^ Y) --> ~(X & Y)
 
 define <2 x i4> @test5_commuted(<2 x i4> %x, <2 x i4> %y) {
 ; CHECK-LABEL: @test5_commuted(
-; CHECK-NEXT:    [[XOR:%.*]] = xor <2 x i4> [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor <2 x i4> [[X]], <i4 -1, i4 -1>
-; CHECK-NEXT:    [[Z:%.*]] = or <2 x i4> [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and <2 x i4> [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor <2 x i4> [[TMP1]], <i4 -1, i4 -1>
 ; CHECK-NEXT:    ret <2 x i4> [[Z]]
 ;
   %xor = xor <2 x i4> %x, %y
   %notx = xor <2 x i4> %x, <i4 -1, i4 -1>
   %z = or <2 x i4> %notx, %xor
   ret <2 x i4> %z
 }
 
 ; Commute the inner 'xor' operands
 ; (Y ^ X) | ~X  --> ~(Y & X)
 
 define i64 @test5_commuted_x_y(i64 %x, i64 %y) {
 ; CHECK-LABEL: @test5_commuted_x_y(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i64 [[Y:%.*]], [[X:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i64 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i64 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i64 [[Y:%.*]], [[X:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i64 [[TMP1]], -1
 ; CHECK-NEXT:    ret i64 [[Z]]
 ;
   %xor = xor i64 %y, %x
   %notx = xor i64 %x, -1
   %z = or i64  %xor, %notx
   ret i64 %z
 }
 
 
 define i8 @test5_extra_use_not(i8 %x, i8 %y, i8* %dst) {
 ; CHECK-LABEL: @test5_extra_use_not(
-; CHECK-NEXT:    [[XOR:%.*]] = xor i8 [[X:%.*]], [[Y:%.*]]
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X]], -1
+; CHECK-NEXT:    [[NOTX:%.*]] = xor i8 [[X:%.*]], -1
 ; CHECK-NEXT:    store i8 [[NOTX]], i8* [[DST:%.*]], align 1
-; CHECK-NEXT:    [[Z:%.*]] = or i8 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i8 [[X]], [[Y:%.*]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i8 [[TMP1]], -1
 ; CHECK-NEXT:    ret i8 [[Z]]
 ;
   %xor = xor i8 %x, %y
   %notx = xor i8 %x, -1
   store i8 %notx, i8* %dst
   %z = or i8 %notx, %xor
   ret i8 %z
 }
 
 
 define i65 @test5_extra_use_xor(i65 %x, i65 %y, i65* %dst) {
 ; CHECK-LABEL: @test5_extra_use_xor(
 ; CHECK-NEXT:    [[XOR:%.*]] = xor i65 [[X:%.*]], [[Y:%.*]]
 ; CHECK-NEXT:    store i65 [[XOR]], i65* [[DST:%.*]], align 4
-; CHECK-NEXT:    [[NOTX:%.*]] = xor i65 [[X]], -1
-; CHECK-NEXT:    [[Z:%.*]] = or i65 [[XOR]], [[NOTX]]
+; CHECK-NEXT:    [[TMP1:%.*]] = and i65 [[X]], [[Y]]
+; CHECK-NEXT:    [[Z:%.*]] = xor i65 [[TMP1]], -1
 ; CHECK-NEXT:    ret i65 [[Z]]
 ;
   %xor = xor i65 %x, %y
   store i65 %xor, i65* %dst
   %notx = xor i65 %x, -1
   %z = or i65 %notx, %xor
   ret i65 %z
 }