From 286198ff043afa7626705fb69c3e9b8873193573 Mon Sep 17 00:00:00 2001 From: "chenglin.bi" Date: Tue, 14 Jun 2022 11:06:10 +0800 Subject: [PATCH] [InstCombine] Optimize lshr+shl+and conversion pattern if `C1` and `C3` are pow2 and `Log2(C3) >= C2`: ((C1 >> X) << C2) & C3 -> X == (Log2(C1)+C2-Log2(C3)) ? C3 : 0 https://alive2.llvm.org/ce/z/zvrkKF Reviewed By: spatel Differential Revision: https://reviews.llvm.org/D127469 --- .../Transforms/InstCombine/InstCombineAndOrXor.cpp | 49 ++++++++++++++-------- llvm/test/Transforms/InstCombine/and.ll | 20 ++++----- 2 files changed, 40 insertions(+), 29 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp index 16435bd..af0efe1 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp @@ -1917,25 +1917,40 @@ Instruction *InstCombinerImpl::visitAnd(BinaryOperator &I) { Constant *C1, *C2; const APInt *C3 = C; Value *X; - if (C3->isPowerOf2() && - match(Op0, m_OneUse(m_LShr(m_Shl(m_ImmConstant(C1), m_Value(X)), - m_ImmConstant(C2)))) && - match(C1, m_Power2())) { - Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1); + if (C3->isPowerOf2()) { Constant *Log2C3 = ConstantInt::get(Ty, C3->countTrailingZeros()); - Constant *LshrC = ConstantExpr::getAdd(C2, Log2C3); - KnownBits KnownLShrc = computeKnownBits(LshrC, 0, nullptr); - if (KnownLShrc.getMaxValue().ult(Width)) { - // iff C1,C3 is pow2 and C2 + cttz(C3) < BitWidth: - // ((C1 << X) >> C2) & C3 -> X == (cttz(C3)+C2-cttz(C1)) ? C3 : 0 - Constant *CmpC = ConstantExpr::getSub(LshrC, Log2C1); - Value *Cmp = Builder.CreateICmpEQ(X, CmpC); - return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3), - ConstantInt::getNullValue(Ty)); + if (match(Op0, m_OneUse(m_LShr(m_Shl(m_ImmConstant(C1), m_Value(X)), + m_ImmConstant(C2)))) && + match(C1, m_Power2())) { + Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1); + Constant *LshrC = ConstantExpr::getAdd(C2, Log2C3); + KnownBits KnownLShrc = computeKnownBits(LshrC, 0, nullptr); + if (KnownLShrc.getMaxValue().ult(Width)) { + // iff C1,C3 is pow2 and C2 + cttz(C3) < BitWidth: + // ((C1 << X) >> C2) & C3 -> X == (cttz(C3)+C2-cttz(C1)) ? C3 : 0 + Constant *CmpC = ConstantExpr::getSub(LshrC, Log2C1); + Value *Cmp = Builder.CreateICmpEQ(X, CmpC); + return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3), + ConstantInt::getNullValue(Ty)); + } + } + + if (match(Op0, m_OneUse(m_Shl(m_LShr(m_ImmConstant(C1), m_Value(X)), + m_ImmConstant(C2)))) && + match(C1, m_Power2())) { + Constant *Log2C1 = ConstantExpr::getExactLogBase2(C1); + Constant *Cmp = + ConstantExpr::getCompare(ICmpInst::ICMP_ULT, Log2C3, C2); + if (Cmp->isZeroValue()) { + // iff C1,C3 is pow2 and Log2(C3) >= C2: + // ((C1 >> X) << C2) & C3 -> X == (cttz(C1)+C2-cttz(C3)) ? C3 : 0 + Constant *ShlC = ConstantExpr::getAdd(C2, Log2C1); + Constant *CmpC = ConstantExpr::getSub(ShlC, Log2C3); + Value *Cmp = Builder.CreateICmpEQ(X, CmpC); + return SelectInst::Create(Cmp, ConstantInt::get(Ty, *C3), + ConstantInt::getNullValue(Ty)); + } } - // TODO: Symmetrical case - // iff C1,C3 is pow2 and Log2(C3) >= C2: - // ((C1 >> X) << C2) & C3 -> X == (cttz(C1)+C2-cttz(C3)) ? C3 : 0 } } diff --git a/llvm/test/Transforms/InstCombine/and.ll b/llvm/test/Transforms/InstCombine/and.ll index eed332b..fcf1db2 100644 --- a/llvm/test/Transforms/InstCombine/and.ll +++ b/llvm/test/Transforms/InstCombine/and.ll @@ -2062,9 +2062,8 @@ define i16 @lshr_shl_pow2_const_xor(i16 %x) { define i16 @lshr_shl_pow2_const_case2(i16 %x) { ; CHECK-LABEL: @lshr_shl_pow2_const_case2( -; CHECK-NEXT: [[LSHR1:%.*]] = lshr i16 8192, [[X:%.*]] -; CHECK-NEXT: [[SHL:%.*]] = shl i16 [[LSHR1]], 4 -; CHECK-NEXT: [[R:%.*]] = and i16 [[SHL]], 32 +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq i16 [[X:%.*]], 12 +; CHECK-NEXT: [[R:%.*]] = select i1 [[TMP1]], i16 32, i16 0 ; CHECK-NEXT: ret i16 [[R]] ; %lshr1 = lshr i16 8192, %x @@ -2102,9 +2101,8 @@ define i16 @lshr_shl_pow2_const_negative_oneuse(i16 %x) { define <3 x i16> @lshr_shl_pow2_const_case1_uniform_vec(<3 x i16> %x) { ; CHECK-LABEL: @lshr_shl_pow2_const_case1_uniform_vec( -; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> , [[X:%.*]] -; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], -; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], +; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> , <3 x i16> zeroinitializer ; CHECK-NEXT: ret <3 x i16> [[R]] ; %lshr = lshr <3 x i16> , %x @@ -2141,9 +2139,8 @@ define <3 x i16> @lshr_shl_pow2_const_case1_non_uniform_vec_negative(<3 x i16> % define <3 x i16> @lshr_shl_pow2_const_case1_undef1_vec(<3 x i16> %x) { ; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef1_vec( -; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> , [[X:%.*]] -; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], -; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], +; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> , <3 x i16> zeroinitializer ; CHECK-NEXT: ret <3 x i16> [[R]] ; %lshr = lshr <3 x i16> , %x @@ -2154,9 +2151,8 @@ define <3 x i16> @lshr_shl_pow2_const_case1_undef1_vec(<3 x i16> %x) { define <3 x i16> @lshr_shl_pow2_const_case1_undef2_vec(<3 x i16> %x) { ; CHECK-LABEL: @lshr_shl_pow2_const_case1_undef2_vec( -; CHECK-NEXT: [[LSHR:%.*]] = lshr <3 x i16> , [[X:%.*]] -; CHECK-NEXT: [[SHL:%.*]] = shl <3 x i16> [[LSHR]], -; CHECK-NEXT: [[R:%.*]] = and <3 x i16> [[SHL]], +; CHECK-NEXT: [[TMP1:%.*]] = icmp eq <3 x i16> [[X:%.*]], +; CHECK-NEXT: [[R:%.*]] = select <3 x i1> [[TMP1]], <3 x i16> , <3 x i16> zeroinitializer ; CHECK-NEXT: ret <3 x i16> [[R]] ; %lshr = lshr <3 x i16> , %x -- 2.7.4