[InstCombine] fold `(a == c && b != c) || (a != c && b == c))` to `(a == c) == (b != c)` (#94915)

resolves https://github.com/llvm/llvm-project/issues/92966

alive proof
https://alive2.llvm.org/ce/z/bLAQBS

2 files changed, 169 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
index d767fa3..19a1234 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
@@ -3421,6 +3421,25 @@ Value *InstCombinerImpl::foldAndOrOfICmps(ICmpInst *LHS, ICmpInst *RHS,
   return foldAndOrOfICmpsUsingRanges(LHS, RHS, IsAnd);
 }
 
+static Value *foldOrOfInversions(BinaryOperator &I,
+                                 InstCombiner::BuilderTy &Builder) {
+  assert(I.getOpcode() == Instruction::Or &&
+         "Simplification only supports or at the moment.");
+
+  Value *Cmp1, *Cmp2, *Cmp3, *Cmp4;
+  if (!match(I.getOperand(0), m_And(m_Value(Cmp1), m_Value(Cmp2))) ||
+      !match(I.getOperand(1), m_And(m_Value(Cmp3), m_Value(Cmp4))))
+    return nullptr;
+
+  // Check if any two pairs of the and operations are inversions of each other.
+  if (isKnownInversion(Cmp1, Cmp3) && isKnownInversion(Cmp2, Cmp4))
+    return Builder.CreateXor(Cmp1, Cmp4);
+  if (isKnownInversion(Cmp1, Cmp4) && isKnownInversion(Cmp2, Cmp3))
+    return Builder.CreateXor(Cmp1, Cmp3);
+
+  return nullptr;
+}
+
 // FIXME: We use commutative matchers (m_c_*) for some, but not all, matches
 // here. We should standardize that construct where it is needed or choose some
 // other way to ensure that commutated variants of patterns are not missed.
@@ -3450,6 +3469,11 @@ Instruction *InstCombinerImpl::visitOr(BinaryOperator &I) {
   if (Instruction *X = foldComplexAndOrPatterns(I, Builder))
     return X;
 
+  // (A & B) | (C & D) -> A ^ D where A == ~C && B == ~D
+  // (A & B) | (C & D) -> A ^ C where A == ~D && B == ~C
+  if (Value *V = foldOrOfInversions(I, Builder))
+    return replaceInstUsesWith(I, V);
+
   // (A&B)|(A&C) -> A&(B|C) etc
   if (Value *V = foldUsingDistributiveLaws(I))
     return replaceInstUsesWith(I, V);
diff --git a/llvm/test/Transforms/InstCombine/fold-a-or-b-zero.ll b/llvm/test/Transforms/InstCombine/fold-a-or-b-zero.ll
new file mode 100644
index 0000000..66a7eb7
--- /dev/null
+++ b/llvm/test/Transforms/InstCombine/fold-a-or-b-zero.ll
@@ -0,0 +1,145 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 5
+; RUN: opt < %s -S -passes=instcombine | FileCheck %s
+
+declare void @use(i1)
+
+define i1 @a_or_b(i32 %a, i32 %b)  {
+; CHECK-LABEL: define i1 @a_or_b(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[A]], 0
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[B]], 0
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_zero = icmp eq i32 %a, 0
+  %b_ne_zero = icmp ne i32 %b, 0
+  %and.1 = and i1 %a_eq_zero, %b_ne_zero
+  %a_ne_zero = icmp ne i32 %a, 0
+  %b_eq_zero = icmp eq i32 %b, 0
+  %and.2 = and i1 %a_ne_zero, %b_eq_zero
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+define i1 @a_or_b_not_inv(i32 %a, i32 %b){
+; CHECK-LABEL: define i1 @a_or_b_not_inv(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:    [[A_EQ_ZERO:%.*]] = icmp eq i32 [[A]], 0
+; CHECK-NEXT:    [[B_NE_ZERO:%.*]] = icmp ne i32 [[B]], 0
+; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[A_EQ_ZERO]], [[B_NE_ZERO]]
+; CHECK-NEXT:    [[A_NE_ZERO:%.*]] = icmp ne i32 [[A]], 0
+; CHECK-NEXT:    [[B_EQ_1:%.*]] = icmp eq i32 [[B]], 1
+; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[A_NE_ZERO]], [[B_EQ_1]]
+; CHECK-NEXT:    [[OR:%.*]] = or i1 [[AND_1]], [[AND_2]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_zero = icmp eq i32 %a, 0
+  %b_ne_zero = icmp ne i32 %b, 0
+  %and.1 = and i1 %a_eq_zero, %b_ne_zero
+  %a_ne_zero = icmp ne i32 %a, 0
+  %b_eq_1 = icmp eq i32 %b, 1
+  %and.2 = and i1 %a_ne_zero, %b_eq_1
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+define i1 @a_or_b_const(i32 %a, i32 %b, i32 %c)  {
+; CHECK-LABEL: define i1 @a_or_b_const(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[A]], [[C]]
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq i32 [[B]], [[C]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_c = icmp eq i32 %a, %c
+  %b_ne_c = icmp ne i32 %b, %c
+  %and.1 = and i1 %a_eq_c, %b_ne_c
+  %a_ne_c = icmp ne i32 %a, %c
+  %b_eq_c = icmp eq i32 %b, %c
+  %and.2 = and i1 %a_ne_c, %b_eq_c
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+define i1 @a_or_b_const2(i32 %a, i32 %b, i32 %c, i32 %d)  {
+; CHECK-LABEL: define i1 @a_or_b_const2(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]], i32 [[D:%.*]]) {
+; CHECK-NEXT:    [[A_EQ_C:%.*]] = icmp eq i32 [[A]], [[C]]
+; CHECK-NEXT:    [[B_EQ_D:%.*]] = icmp eq i32 [[B]], [[D]]
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[A_EQ_C]], [[B_EQ_D]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_c = icmp eq i32 %a, %c
+  %b_ne_d = icmp ne i32 %b, %d
+  %and.1 = and i1 %a_eq_c, %b_ne_d
+  %a_ne_c = icmp ne i32 %a, %c
+  %b_eq_d = icmp eq i32 %b, %d
+  %and.2 = and i1 %a_ne_c, %b_eq_d
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+define i1 @a_or_b_nullptr(ptr %a, ptr %b) {
+; CHECK-LABEL: define i1 @a_or_b_nullptr(
+; CHECK-SAME: ptr [[A:%.*]], ptr [[B:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq ptr [[A]], null
+; CHECK-NEXT:    [[TMP2:%.*]] = icmp eq ptr [[B]], null
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[TMP1]], [[TMP2]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_null = icmp eq ptr %a, null
+  %b_null = icmp eq ptr %b, null
+  %a_not_null = icmp ne ptr %a, null
+  %b_not_null = icmp ne ptr %b, null
+  %and.1 = and i1 %a_null, %b_not_null
+  %and.2 = and i1 %a_not_null, %b_null
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+define i1 @a_or_b_multiple_uses(i32 %a, i32 %b)  {
+; CHECK-LABEL: define i1 @a_or_b_multiple_uses(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[A]], 0
+; CHECK-NEXT:    [[A_NE_ZERO:%.*]] = icmp ne i32 [[A]], 0
+; CHECK-NEXT:    [[B_EQ_ZERO:%.*]] = icmp eq i32 [[B]], 0
+; CHECK-NEXT:    [[AND_2:%.*]] = and i1 [[A_NE_ZERO]], [[B_EQ_ZERO]]
+; CHECK-NEXT:    call void @use(i1 [[AND_2]])
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[TMP1]], [[B_EQ_ZERO]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_zero = icmp eq i32 %a, 0
+  %b_ne_zero = icmp ne i32 %b, 0
+  %and.1 = and i1 %a_eq_zero, %b_ne_zero
+  %a_ne_zero = icmp ne i32 %a, 0
+  %b_eq_zero = icmp eq i32 %b, 0
+  %and.2 = and i1 %a_ne_zero, %b_eq_zero
+  call void @use(i1 %and.2)
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+define i1 @a_or_b_multiple_uses_2(i32 %a, i32 %b)  {
+; CHECK-LABEL: define i1 @a_or_b_multiple_uses_2(
+; CHECK-SAME: i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:    [[A_EQ_ZERO:%.*]] = icmp eq i32 [[A]], 0
+; CHECK-NEXT:    [[B_NE_ZERO:%.*]] = icmp ne i32 [[B]], 0
+; CHECK-NEXT:    call void @use(i1 [[B_NE_ZERO]])
+; CHECK-NEXT:    [[AND_1:%.*]] = and i1 [[A_EQ_ZERO]], [[B_NE_ZERO]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[B]], 0
+; CHECK-NEXT:    call void @use(i1 [[AND_1]])
+; CHECK-NEXT:    [[OR:%.*]] = xor i1 [[A_EQ_ZERO]], [[TMP1]]
+; CHECK-NEXT:    ret i1 [[OR]]
+;
+  %a_eq_zero = icmp eq i32 %a, 0
+  %b_ne_zero = icmp ne i32 %b, 0
+  call void @use(i1 %b_ne_zero)
+  %and.1 = and i1 %a_eq_zero, %b_ne_zero
+  %a_ne_zero = icmp ne i32 %a, 0
+  %b_eq_zero = icmp eq i32 %b, 0
+  %and.2 = and i1 %a_ne_zero, %b_eq_zero
+  call void @use(i1 %and.1)
+  %or = or i1 %and.1, %and.2
+  ret i1 %or
+}
+
+