diff options
author | Zain Jaffal <zain@jjaffal.com> | 2024-06-23 10:39:07 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-06-23 10:39:07 +0100 |
commit | f7fc72e281e26082d98b26c95c7ffc93393b3920 (patch) | |
tree | 8a818c7f7160388034488566d0858fa628ae02cd | |
parent | 3ae6755719c6dfc07761b4e9bdac8c86bcb41734 (diff) | |
download | llvm-f7fc72e281e26082d98b26c95c7ffc93393b3920.zip llvm-f7fc72e281e26082d98b26c95c7ffc93393b3920.tar.gz llvm-f7fc72e281e26082d98b26c95c7ffc93393b3920.tar.bz2 |
[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
-rw-r--r-- | llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp | 24 | ||||
-rw-r--r-- | llvm/test/Transforms/InstCombine/fold-a-or-b-zero.ll | 145 |
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 +} + + |