[InstCombine] Fold ((A&B)^A)|((A&B)^B) to A^B

[marcauberer]

Summary

Depends on D159379

((A & B) ^ A) | ((A & B) ^ B) -> A ^ B
(A ^ (A & B)) | (B ^ (A & B)) -> A ^ B
((A & B) ^ B) | ((A & B) ^ A) -> A ^ B
(B ^ (A & B)) | (A ^ (A & B)) -> A ^ B

Alive2: https://alive2.llvm.org/ce/z/i44xmq
Baseline tests: https://reviews.llvm.org/D159379

[goldstein.w.n]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3669

1. the m_Xor -> m_c_Xor
2. Put this in a lambda so you don't need to duplicate the match logic and just do SomeFuncName(Op0, Op1) / SomeFuncName(Op1, Op0).

[marcauberer]

Use lambda to avoid code duplication

[marcauberer]

Reflect changes to tests

[huihuiz]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3668

Remove "; Result != nullptr". Not needed.

3670

Same.

[marcauberer]

Remove unnecessary nullptr checks

[marcauberer]

Can someone land the baseline tests patch and this patch for me? I do not have commit access.

[huihuiz]

I can help land this patch and the baseline test.
Just give it more hours in case other people catch anything different.

[nikic]

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

3662

Why does this transform have a one-use limitation?

[marcauberer]

@nikic see https://github.com/llvm/llvm-project/pull/66419

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (match(&I, m_c_Or(m_OneUse(m_AShr(
                              m_SpecificInt(Ty->getScalarSizeInBits() - 1))),
                          m_Deferred(X)))) {
       Value *NewICmpInst = Builder.CreateICmpSGT(X, Y);
       Value *AllOnes = ConstantInt::getAllOnesValue(Ty);
       return SelectInst::Create(NewICmpInst, AllOnes, X);
     }
   }
 
+  {
+    // ((A & B) ^ A) | ((A & B) ^ B) -> A ^ B
+    // (A ^ (A & B)) | (B ^ (A & B)) -> A ^ B
+    // ((A & B) ^ B) | ((A & B) ^ A) -> A ^ B
+    // (B ^ (A & B)) | (A ^ (A & B)) -> A ^ B
+    const auto TryXorOpt = [&](Value *Lhs, Value *Rhs) -> Instruction * {
+      if (match(Lhs, m_OneUse(m_c_Xor(m_And(m_Value(A), m_Value(B)),
+                                      m_Deferred(A)))) &&
+          match(Rhs, m_OneUse(m_c_Xor(m_And(m_Specific(A), m_Specific(B)),
+                                      m_Deferred(B))))) {
+        return BinaryOperator::CreateXor(A, B);
+      }
+      return nullptr;
+    };
+
+    if (Instruction *Result = TryXorOpt(Op0, Op1); Result != nullptr)
+      return Result;
+    if (Instruction *Result = TryXorOpt(Op1, Op0); Result != nullptr)
+      return Result;
+  }
+
   if (Instruction *V =
           canonicalizeCondSignextOfHighBitExtractToSignextHighBitExtract(I))
     return V;
 
   CmpInst::Predicate Pred;
   Value *Mul, *Ov, *MulIsNotZero, *UMulWithOv;
   // Check if the OR weakens the overflow condition for umul.with.overflow by
   // treating any non-zero result as overflow. In that case, we overflow if both

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -passes=instcombine -S | FileCheck %s
 
 declare void @use.i3(i1)
 declare void @use.i5(i5)
 declare void @use.i32(i5)
 
 define i1 @or_xor_xor_normal_variant1(i1 %a, i1 %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_variant1(
-; CHECK-NEXT:    [[AND:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i1 [[AND]], [[A]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i1 [[AND]], [[B]]
-; CHECK-NEXT:    [[OR:%.*]] = or i1 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i1 [[OR]]
 ;
   %and = and i1 %a, %b
   %xor1 = xor i1 %and, %a
   %xor2 = xor i1 %and, %b
   %or = or i1 %xor1, %xor2
   ret i1 %or
 }
 
 define i8 @or_xor_xor_normal_variant2(i8 %a, i8 %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_variant2(
-; CHECK-NEXT:    [[AND:%.*]] = and i8 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i8 [[AND]], [[B]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i8 [[AND]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i8 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i8 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret i8 [[OR]]
 ;
   %and = and i8 %a, %b
   %xor1 = xor i8 %and, %b
   %xor2 = xor i8 %a, %and
   %or = or i8 %xor1, %xor2
   ret i8 %or
 }
 
 define i16 @or_xor_xor_normal_variant3(i16 %a, i16 %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_variant3(
-; CHECK-NEXT:    [[AND:%.*]] = and i16 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i16 [[AND]], [[B]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i16 [[AND]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i16 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i16 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i16 [[OR]]
 ;
   %and = and i16 %b, %a
   %xor1 = xor i16 %b, %and
   %xor2 = xor i16 %a, %and
   %or = or i16 %xor1, %xor2
   ret i16 %or
 }
 
 define i64 @or_xor_xor_normal_variant4(i64 %a, i64 %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_variant4(
-; CHECK-NEXT:    [[AND:%.*]] = and i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i64 [[AND]], [[B]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i64 [[AND]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i64 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i64 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    ret i64 [[OR]]
 ;
   %and = and i64 %b, %a
   %xor1 = xor i64 %and, %b
   %xor2 = xor i64 %and, %a
   %or = or i64 %xor1, %xor2
   ret i64 %or
 }
 
 define i32 @or_xor_xor_normal_binops(i32 %aa, i32 %bb, i32 %cc) {
 ; CHECK-LABEL: @or_xor_xor_normal_binops(
-; CHECK-NEXT:    [[A:%.*]] = xor i32 [[AA:%.*]], [[CC:%.*]]
-; CHECK-NEXT:    [[B:%.*]] = xor i32 [[BB:%.*]], [[CC]]
-; CHECK-NEXT:    [[AND:%.*]] = and i32 [[B]], [[A]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 [[B]], [[AND]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i32 [[A]], [[AND]]
-; CHECK-NEXT:    [[OR:%.*]] = or i32 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i32 [[BB:%.*]], [[AA:%.*]]
 ; CHECK-NEXT:    ret i32 [[OR]]
 ;
   %a = xor i32 %aa, %cc
   %b = xor i32 %bb, %cc
 
   %and = and i32 %b, %a
   %xor1 = xor i32 %b, %and
   %xor2 = xor i32 %a, %and
   %or = or i32 %xor1, %xor2
   ret i32 %or
 }
 
 define <3 x i1> @or_xor_xor_normal_vector(<3 x i1> %a, <3 x i1> %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_vector(
-; CHECK-NEXT:    [[AND:%.*]] = and <3 x i1> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[XOR1:%.*]] = xor <3 x i1> [[AND]], [[B]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor <3 x i1> [[AND]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or <3 x i1> [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor <3 x i1> [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    ret <3 x i1> [[OR]]
 ;
   %and = and <3 x i1> %a, %b
   %xor1 = xor <3 x i1> %and, %b
   %xor2 = xor <3 x i1> %and, %a
   %or = or <3 x i1> %xor1, %xor2
   ret <3 x i1> %or
 }
 
 define i3 @or_xor_xor_normal_multiple_uses_and(i3 %a, i3 %b) {
 ; CHECK-LABEL: @or_xor_xor_normal_multiple_uses_and(
 ; CHECK-NEXT:    [[AND:%.*]] = and i3 [[A:%.*]], [[B:%.*]]
 ; CHECK-NEXT:    call void @use.i3(i3 [[AND]])
-; CHECK-NEXT:    [[XOR1:%.*]] = xor i3 [[AND]], [[B]]
-; CHECK-NEXT:    [[XOR2:%.*]] = xor i3 [[AND]], [[A]]
-; CHECK-NEXT:    [[OR:%.*]] = or i3 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i3 [[A]], [[B]]
 ; CHECK-NEXT:    ret i3 [[OR]]
 ;
   %and = and i3 %a, %b
   call void @use.i3(i3 %and)
   %xor1 = xor i3 %b, %and
   %xor2 = xor i3 %a, %and
   %or = or i3 %xor1, %xor2
   ret i3 %or