From f879c9b796210d0b2407d022e216cc4d907818a3 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Wed, 5 Aug 2020 13:41:05 -0400 Subject: [PATCH] [InstSimplify] fold icmp with mul nuw and constant operands https://rise4fun.com/Alive/pZEr Name: mul nuw with icmp eq Pre: (C2 %u C1) != 0 %a = mul nuw i8 %x, C1 %r = icmp eq i8 %a, C2 => %r = false Name: mul nuw with icmp ne Pre: (C2 %u C1) != 0 %a = mul nuw i8 %x, C1 %r = icmp ne i8 %a, C2 => %r = true There are potentially several other transforms we need to add based on: D51625 ...but it doesn't look like there was follow-up to that patch. --- llvm/lib/Analysis/InstructionSimplify.cpp | 8 +++++ llvm/test/Transforms/InstCombine/icmp-mul.ll | 8 ++--- llvm/test/Transforms/InstSimplify/icmp-constant.ll | 34 ++++++++++++---------- 3 files changed, 29 insertions(+), 21 deletions(-) diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index 148ad21..004d985 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -2750,6 +2750,14 @@ static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, return ConstantInt::getFalse(ITy); } + // (mul nuw X, MulC) != C --> true (if C is not a multiple of MulC) + // (mul nuw X, MulC) == C --> false (if C is not a multiple of MulC) + const APInt *MulC; + if (ICmpInst::isEquality(Pred) && + match(LHS, m_NUWMul(m_Value(), m_APIntAllowUndef(MulC))) && + C->urem(*MulC) != 0) + return ConstantInt::get(ITy, Pred == ICmpInst::ICMP_NE); + return nullptr; } diff --git a/llvm/test/Transforms/InstCombine/icmp-mul.ll b/llvm/test/Transforms/InstCombine/icmp-mul.ll index d671810..7f122f5 100644 --- a/llvm/test/Transforms/InstCombine/icmp-mul.ll +++ b/llvm/test/Transforms/InstCombine/icmp-mul.ll @@ -141,9 +141,7 @@ define i1 @ne_rem_zero(i8 %x) { define i1 @eq_rem_nz(i8 %x) { ; CHECK-LABEL: @eq_rem_nz( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 5 -; CHECK-NEXT: [[B:%.*]] = icmp eq i8 [[A]], 31 -; CHECK-NEXT: ret i1 [[B]] +; CHECK-NEXT: ret i1 false ; %a = mul nuw i8 %x, 5 %b = icmp eq i8 %a, 31 @@ -152,9 +150,7 @@ define i1 @eq_rem_nz(i8 %x) { define i1 @ne_rem_nz(i8 %x) { ; CHECK-LABEL: @ne_rem_nz( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 5 -; CHECK-NEXT: [[B:%.*]] = icmp ne i8 [[A]], 31 -; CHECK-NEXT: ret i1 [[B]] +; CHECK-NEXT: ret i1 true ; %a = mul nuw i8 %x, 5 %b = icmp ne i8 %a, 31 diff --git a/llvm/test/Transforms/InstSimplify/icmp-constant.ll b/llvm/test/Transforms/InstSimplify/icmp-constant.ll index 7cde4f2..88ffe2b 100644 --- a/llvm/test/Transforms/InstSimplify/icmp-constant.ll +++ b/llvm/test/Transforms/InstSimplify/icmp-constant.ll @@ -810,11 +810,11 @@ define i1 @eq_shl_by_variable_produces_poison(i8 %x) { ret i1 %cmp } +; No overflow, so mul constant must be a factor of cmp constant. + define i1 @mul_nuw_urem_cmp_constant1(i8 %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant1( -; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], 43 -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[M]], 42 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %m = mul nuw i8 %x, 43 %r = icmp eq i8 %m, 42 @@ -825,31 +825,29 @@ define i1 @mul_nuw_urem_cmp_constant1(i8 %x) { define <2 x i1> @mul_nuw_urem_cmp_constant_vec_splat(<2 x i8> %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant_vec_splat( -; CHECK-NEXT: [[M:%.*]] = mul nuw <2 x i8> [[X:%.*]], -; CHECK-NEXT: [[R:%.*]] = icmp ne <2 x i8> [[M]], -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> ; %m = mul nuw <2 x i8> %x, %r = icmp ne <2 x i8> %m, ret <2 x i1> %r } +; Undefs in vector constants are ok. + define <2 x i1> @mul_nuw_urem_cmp_constant_vec_splat_undef1(<2 x i8> %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant_vec_splat_undef1( -; CHECK-NEXT: [[M:%.*]] = mul nuw <2 x i8> [[X:%.*]], -; CHECK-NEXT: [[R:%.*]] = icmp ne <2 x i8> [[M]], -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> ; %m = mul nuw <2 x i8> %x, %r = icmp ne <2 x i8> %m, ret <2 x i1> %r } +; Undefs in vector constants are ok. + define <2 x i1> @mul_nuw_urem_cmp_constant_vec_splat_undef2(<2 x i8> %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant_vec_splat_undef2( -; CHECK-NEXT: [[M:%.*]] = mul nuw <2 x i8> [[X:%.*]], -; CHECK-NEXT: [[R:%.*]] = icmp ne <2 x i8> [[M]], -; CHECK-NEXT: ret <2 x i1> [[R]] +; CHECK-NEXT: ret <2 x i1> ; %m = mul nuw <2 x i8> %x, %r = icmp ne <2 x i8> %m, @@ -860,15 +858,15 @@ define <2 x i1> @mul_nuw_urem_cmp_constant_vec_splat_undef2(<2 x i8> %x) { define i1 @mul_nuw_urem_cmp_constant2(i8 %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant2( -; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], -42 -; CHECK-NEXT: [[R:%.*]] = icmp eq i8 [[M]], -84 -; CHECK-NEXT: ret i1 [[R]] +; CHECK-NEXT: ret i1 false ; %m = mul nuw i8 %x, -42 %r = icmp eq i8 %m, -84 ret i1 %r } +; Negative test - require nuw. + define i1 @mul_urem_cmp_constant1(i8 %x) { ; CHECK-LABEL: @mul_urem_cmp_constant1( ; CHECK-NEXT: [[M:%.*]] = mul i8 [[X:%.*]], 43 @@ -880,6 +878,8 @@ define i1 @mul_urem_cmp_constant1(i8 %x) { ret i1 %r } +; Negative test - x could be 0. + define i1 @mul_nuw_urem_cmp_constant0(i8 %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant0( ; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], 23 @@ -891,6 +891,8 @@ define i1 @mul_nuw_urem_cmp_constant0(i8 %x) { ret i1 %r } +; Negative test - cmp constant is multiple of mul constant. + define i1 @mul_nuw_urem_cmp_constant_is_0(i8 %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_constant_is_0( ; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], 42 @@ -902,6 +904,8 @@ define i1 @mul_nuw_urem_cmp_constant_is_0(i8 %x) { ret i1 %r } +; Negative test - cmp constant is multiple (treated as unsigned). + define i1 @mul_nuw_urem_cmp_neg_constant_is_0(i8 %x) { ; CHECK-LABEL: @mul_nuw_urem_cmp_neg_constant_is_0( ; CHECK-NEXT: [[M:%.*]] = mul nuw i8 [[X:%.*]], 43 -- 2.7.4