From 1b7fc870206a44474ea72b1b6c0c2653582a7987 Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Sat, 15 Sep 2018 12:04:13 +0000 Subject: [PATCH] [InstCombine] Inefficient pattern for high-bits checking 3 (PR38708) Summary: It is sometimes important to check that some newly-computed value is non-negative and only n bits wide (where n is a variable.) There are many ways to check that: https://godbolt.org/z/o4RB8D The last variant seems best? (I'm sure there are some other variations i haven't thought of..) The last (as far i know?) pattern, non-canonical due to the extra use. https://godbolt.org/z/aCMsPk https://rise4fun.com/Alive/I6f https://bugs.llvm.org/show_bug.cgi?id=38708 Reviewers: spatel, craig.topper, RKSimon Reviewed By: spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D52062 llvm-svn: 342321 --- .../Transforms/InstCombine/InstCombineCompares.cpp | 17 ++++++++----- ...and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll | 28 +++++++++++----------- ...and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll | 28 +++++++++++----------- 3 files changed, 39 insertions(+), 34 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index a295f65..5f8bf84 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -4624,8 +4624,8 @@ static Instruction *canonicalizeICmpBool(ICmpInst &I, } // Transform pattern like: -// (1 << Y) u<= X or ~(-1 << Y) u< X -// (1 << Y) u> X or ~(-1 << Y) u>= X +// (1 << Y) u<= X or ~(-1 << Y) u< X or ((1 << Y)+(-1)) u< X +// (1 << Y) u> X or ~(-1 << Y) u>= X or ((1 << Y)+(-1)) u>= X // Into: // (X l>> Y) != 0 // (X l>> Y) == 0 @@ -4649,10 +4649,15 @@ static Instruction *foldICmpWithHighBitMask(ICmpInst &Cmp, default: return nullptr; } - } else if (match(&Cmp, - m_c_ICmp(Pred, - m_OneUse(m_Not(m_Shl(m_AllOnes(), m_Value(Y)))), - m_Value(X)))) { + } else if (match(&Cmp, m_c_ICmp(Pred, + m_OneUse(m_CombineOr( + m_Not(m_Shl(m_AllOnes(), m_Value(Y))), + m_Add(m_Shl(m_One(), m_Value(Y)), + m_AllOnes()))), + m_Value(X)))) { + // The variant with 'add' is not canonical, (the variant with 'not' is) + // we only get it because it has extra uses, and can't be canonicalized, + // We want X to be the icmp's second operand, so swap predicate if it isn't. if (Cmp.getOperand(0) == X) Pred = Cmp.getSwappedPredicate(); diff --git a/llvm/test/Transforms/InstCombine/icmp-uge-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll b/llvm/test/Transforms/InstCombine/icmp-uge-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll index d3256aa..a3d9cca7 100644 --- a/llvm/test/Transforms/InstCombine/icmp-uge-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll +++ b/llvm/test/Transforms/InstCombine/icmp-uge-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-eq-of-lshr-val-by-bits-and-0.ll @@ -22,8 +22,8 @@ define i1 @p0(i8 %val, i8 %bits) { ; CHECK-LABEL: @p0( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 -; CHECK-NEXT: [[R:%.*]] = icmp uge i8 [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[VAL_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits @@ -41,8 +41,8 @@ define <2 x i1> @p1_vec(<2 x i8> %val, <2 x i8> %bits) { ; CHECK-LABEL: @p1_vec( ; CHECK-NEXT: [[T0:%.*]] = shl <2 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use2i8(<2 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <2 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp uge <2 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <2 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq <2 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <2 x i1> [[R]] ; %t0 = shl <2 x i8> , %bits @@ -56,8 +56,8 @@ define <3 x i1> @p2_vec_undef0(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef0( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp uge <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -71,8 +71,8 @@ define <3 x i1> @p2_vec_undef1(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef1( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp uge <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -86,8 +86,8 @@ define <3 x i1> @p2_vec_undef2(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef2( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp uge <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -107,9 +107,9 @@ define i1 @c0(i8 %bits) { ; CHECK-LABEL: @c0( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 ; CHECK-NEXT: [[VAL:%.*]] = call i8 @gen8() -; CHECK-NEXT: [[R:%.*]] = icmp ule i8 [[VAL]], [[T1]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[VAL_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits @@ -125,11 +125,11 @@ define i1 @both(i8 %bits0, i8 %bits1) { ; CHECK-LABEL: @both( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS0:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 ; CHECK-NEXT: [[T2:%.*]] = shl i8 1, [[BITS1:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T2]]) ; CHECK-NEXT: [[T3:%.*]] = add i8 [[T2]], -1 -; CHECK-NEXT: [[R:%.*]] = icmp uge i8 [[T1]], [[T3]] +; CHECK-NEXT: [[T3_HIGHBITS:%.*]] = lshr i8 [[T3]], [[BITS0]] +; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[T3_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits0 diff --git a/llvm/test/Transforms/InstCombine/icmp-ult-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll b/llvm/test/Transforms/InstCombine/icmp-ult-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll index d68dd71..2de7e43 100644 --- a/llvm/test/Transforms/InstCombine/icmp-ult-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll +++ b/llvm/test/Transforms/InstCombine/icmp-ult-of-add-of-shl-one-by-bits-to-allones-and-val-to-icmp-ne-of-lshr-val-by-bits-and-0.ll @@ -22,8 +22,8 @@ define i1 @p0(i8 %val, i8 %bits) { ; CHECK-LABEL: @p0( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 -; CHECK-NEXT: [[R:%.*]] = icmp ult i8 [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne i8 [[VAL_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits @@ -41,8 +41,8 @@ define <2 x i1> @p1_vec(<2 x i8> %val, <2 x i8> %bits) { ; CHECK-LABEL: @p1_vec( ; CHECK-NEXT: [[T0:%.*]] = shl <2 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use2i8(<2 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <2 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp ult <2 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <2 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne <2 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <2 x i1> [[R]] ; %t0 = shl <2 x i8> , %bits @@ -56,8 +56,8 @@ define <3 x i1> @p2_vec_undef0(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef0( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp ult <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -71,8 +71,8 @@ define <3 x i1> @p2_vec_undef1(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef1( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp ult <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -86,8 +86,8 @@ define <3 x i1> @p2_vec_undef2(<3 x i8> %val, <3 x i8> %bits) { ; CHECK-LABEL: @p2_vec_undef2( ; CHECK-NEXT: [[T0:%.*]] = shl <3 x i8> , [[BITS:%.*]] ; CHECK-NEXT: call void @use3i8(<3 x i8> [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add <3 x i8> [[T0]], -; CHECK-NEXT: [[R:%.*]] = icmp ult <3 x i8> [[T1]], [[VAL:%.*]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr <3 x i8> [[VAL:%.*]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne <3 x i8> [[VAL_HIGHBITS]], zeroinitializer ; CHECK-NEXT: ret <3 x i1> [[R]] ; %t0 = shl <3 x i8> , %bits @@ -107,9 +107,9 @@ define i1 @c0(i8 %bits) { ; CHECK-LABEL: @c0( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 ; CHECK-NEXT: [[VAL:%.*]] = call i8 @gen8() -; CHECK-NEXT: [[R:%.*]] = icmp ugt i8 [[VAL]], [[T1]] +; CHECK-NEXT: [[VAL_HIGHBITS:%.*]] = lshr i8 [[VAL]], [[BITS]] +; CHECK-NEXT: [[R:%.*]] = icmp ne i8 [[VAL_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits @@ -125,11 +125,11 @@ define i1 @both(i8 %bits0, i8 %bits1) { ; CHECK-LABEL: @both( ; CHECK-NEXT: [[T0:%.*]] = shl i8 1, [[BITS0:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T0]]) -; CHECK-NEXT: [[T1:%.*]] = add i8 [[T0]], -1 ; CHECK-NEXT: [[T2:%.*]] = shl i8 1, [[BITS1:%.*]] ; CHECK-NEXT: call void @use8(i8 [[T2]]) ; CHECK-NEXT: [[T3:%.*]] = add i8 [[T2]], -1 -; CHECK-NEXT: [[R:%.*]] = icmp ult i8 [[T1]], [[T3]] +; CHECK-NEXT: [[T3_HIGHBITS:%.*]] = lshr i8 [[T3]], [[BITS0]] +; CHECK-NEXT: [[R:%.*]] = icmp ne i8 [[T3_HIGHBITS]], 0 ; CHECK-NEXT: ret i1 [[R]] ; %t0 = shl i8 1, %bits0 -- 2.7.4