From 98855059674cf1b6b415f8c543f2a923771fed27 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Mon, 30 Jan 2023 15:34:29 -0500 Subject: [PATCH] [InstCombine] reduce icmp_eq0-of-and-of-select-of-constants This is the most basic patch to handle fixing issue #57666. D133919 proposes to handle much more than this in a single patch, but I've used 10 regression tests just to make sure this part is doing what I expected and nothing more, and it already shows even more potential TODO items. The more general proofs from D133919 are correct, but I want to enable this in smaller steps to reduce risk: https://alive2.llvm.org/ce/z/RrVEyX Differential Revision: https://reviews.llvm.org/D142847 --- .../Transforms/InstCombine/InstCombineCompares.cpp | 19 ++++++++++++++ llvm/test/Transforms/InstCombine/icmp-select.ll | 30 +++++++++++++++------- 2 files changed, 40 insertions(+), 9 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index 5e0dac7..8ff75d5 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1888,6 +1888,25 @@ Instruction *InstCombinerImpl::foldICmpAndConstant(ICmpInst &Cmp, return new ICmpInst(NewPred, X, SubOne(cast(Cmp.getOperand(1)))); } + // If we are testing the intersection of 2 select-of-nonzero-constants with no + // common bits set, it's the same as checking if exactly one select condition + // is set: + // ((A ? TC : FC) & (B ? TC : FC)) == 0 --> xor A, B + // TODO: Generalize for non-constant values. + // TODO: Invert with a "ne" predicate. + // TODO: Handle signed/unsigned predicates. + // TODO: Handle other bitwise logic connectors. + // TODO: Extend to handle a non-zero compare constant. + if (Pred == CmpInst::ICMP_EQ && C.isZero()) { + Value *A, *B; + const APInt *TC, *FC; + if (match(X, m_Select(m_Value(A), m_APInt(TC), m_APInt(FC))) && + match(Y, + m_Select(m_Value(B), m_SpecificInt(*TC), m_SpecificInt(*FC))) && + !TC->isZero() && !FC->isZero() && !TC->intersects(*FC)) + return BinaryOperator::CreateXor(A, B); + } + // ((zext i1 X) & Y) == 0 --> !((trunc Y) & X) // ((zext i1 X) & Y) != 0 --> ((trunc Y) & X) // ((zext i1 X) & Y) == 1 --> ((trunc Y) & X) diff --git a/llvm/test/Transforms/InstCombine/icmp-select.ll b/llvm/test/Transforms/InstCombine/icmp-select.ll index 0c7b145..315a22e 100644 --- a/llvm/test/Transforms/InstCombine/icmp-select.ll +++ b/llvm/test/Transforms/InstCombine/icmp-select.ll @@ -262,10 +262,7 @@ define i1 @umin_seq_comparison(i8 %x, i8 %y) { define i1 @select_constants_and_icmp_eq0(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0( -; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 2, i8 1 -; CHECK-NEXT: [[S2:%.*]] = select i1 [[Y:%.*]], i8 2, i8 1 -; CHECK-NEXT: [[AND:%.*]] = and i8 [[S1]], [[S2]] -; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[AND]], 0 +; CHECK-NEXT: [[CMP:%.*]] = xor i1 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[CMP]] ; %s1 = select i1 %x, i8 2, i8 1 @@ -275,6 +272,8 @@ define i1 @select_constants_and_icmp_eq0(i1 %x, i1 %y) { ret i1 %cmp } +; extra uses on all intermediates are ok + define i1 @select_constants_and_icmp_eq0_uses(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_uses( ; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 2, i8 1 @@ -283,7 +282,7 @@ define i1 @select_constants_and_icmp_eq0_uses(i1 %x, i1 %y) { ; CHECK-NEXT: call void @use(i8 [[S2]]) ; CHECK-NEXT: [[AND:%.*]] = and i8 [[S1]], [[S2]] ; CHECK-NEXT: call void @use(i8 [[AND]]) -; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[AND]], 0 +; CHECK-NEXT: [[CMP:%.*]] = xor i1 [[X]], [[Y]] ; CHECK-NEXT: ret i1 [[CMP]] ; %s1 = select i1 %x, i8 2, i8 1 @@ -296,12 +295,11 @@ define i1 @select_constants_and_icmp_eq0_uses(i1 %x, i1 %y) { ret i1 %cmp } +; vector splat constants are ok + define <2 x i1> @select_constants_and_icmp_eq0_vec_splat(<2 x i1> %x, <2 x i1> %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_vec_splat( -; CHECK-NEXT: [[S1:%.*]] = select <2 x i1> [[X:%.*]], <2 x i9> , <2 x i9> -; CHECK-NEXT: [[S2:%.*]] = select <2 x i1> [[Y:%.*]], <2 x i9> , <2 x i9> -; CHECK-NEXT: [[AND:%.*]] = and <2 x i9> [[S1]], [[S2]] -; CHECK-NEXT: [[CMP:%.*]] = icmp eq <2 x i9> [[AND]], zeroinitializer +; CHECK-NEXT: [[CMP:%.*]] = xor <2 x i1> [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret <2 x i1> [[CMP]] ; %s1 = select <2 x i1> %x, <2 x i9> , <2 x i9> @@ -311,6 +309,8 @@ define <2 x i1> @select_constants_and_icmp_eq0_vec_splat(<2 x i1> %x, <2 x i1> % ret <2 x i1> %cmp } +; common bit set - simplified via known bits + define i1 @select_constants_and_icmp_eq0_common_bit(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_common_bit( ; CHECK-NEXT: ret i1 false @@ -322,6 +322,8 @@ define i1 @select_constants_and_icmp_eq0_common_bit(i1 %x, i1 %y) { ret i1 %cmp } +; negative test - need matching constants + define i1 @select_constants_and_icmp_eq0_no_common_op1(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_no_common_op1( ; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 16, i8 3 @@ -337,6 +339,8 @@ define i1 @select_constants_and_icmp_eq0_no_common_op1(i1 %x, i1 %y) { ret i1 %cmp } +; negative test - need matching constants + define i1 @select_constants_and_icmp_eq0_no_common_op2(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_no_common_op2( ; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 16, i8 3 @@ -352,6 +356,8 @@ define i1 @select_constants_and_icmp_eq0_no_common_op2(i1 %x, i1 %y) { ret i1 %cmp } +; reduces via FoldOpInstSelect, but this could be a simple 'or' + define i1 @select_constants_and_icmp_eq0_zero_tval(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_zero_tval( ; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[X:%.*]], i1 true, i1 [[Y:%.*]] @@ -364,6 +370,8 @@ define i1 @select_constants_and_icmp_eq0_zero_tval(i1 %x, i1 %y) { ret i1 %cmp } +; reduces via FoldOpInstSelect, but this could be a simple 'not-of-and' + define i1 @select_constants_and_icmp_eq0_zero_fval(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq0_zero_fval( ; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[X:%.*]], i1 [[Y:%.*]], i1 false @@ -377,6 +385,8 @@ define i1 @select_constants_and_icmp_eq0_zero_fval(i1 %x, i1 %y) { ret i1 %cmp } +; TODO: x & y + define i1 @select_constants_and_icmp_eq_tval(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq_tval( ; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 6, i8 1 @@ -392,6 +402,8 @@ define i1 @select_constants_and_icmp_eq_tval(i1 %x, i1 %y) { ret i1 %cmp } +; TODO: ~(x | y) + define i1 @select_constants_and_icmp_eq_fval(i1 %x, i1 %y) { ; CHECK-LABEL: @select_constants_and_icmp_eq_fval( ; CHECK-NEXT: [[S1:%.*]] = select i1 [[X:%.*]], i8 12, i8 3 -- 2.7.4