From c66169136fe667d653ff40ba4bd9f6047702e93c Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Wed, 5 Aug 2020 17:04:21 -0400 Subject: [PATCH] [InstCombine] fold icmp with 'mul nsw/nuw' and constant operands This also removes a more specific fold that only handled icmp with 0. https://rise4fun.com/Alive/sdM9 Name: mul nsw with icmp eq Pre: (C1 != 0) && (C2 % C1) == 0 %a = mul nsw i8 %x, C1 %r = icmp eq i8 %a, C2 => %r = icmp eq i8 %x, C2 / C1 Name: mul nuw with icmp eq Pre: (C1 != 0) && (C2 %u C1) == 0 %a = mul nuw i8 %x, C1 %r = icmp eq i8 %a, C2 => %r = icmp eq i8 %x, C2 /u C1 Name: mul nsw with icmp ne Pre: (C1 != 0) && (C2 % C1) == 0 %a = mul nsw i8 %x, C1 %r = icmp ne i8 %a, C2 => %r = icmp ne i8 %x, C2 / C1 Name: mul nuw with icmp ne Pre: (C1 != 0) && (C2 %u C1) == 0 %a = mul nuw i8 %x, C1 %r = icmp ne i8 %a, C2 => %r = icmp ne i8 %x, C2 /u C1 --- .../Transforms/InstCombine/InstCombineCompares.cpp | 26 +++++++++++++--------- llvm/test/Transforms/InstCombine/icmp-mul.ll | 24 +++++++++++--------- 2 files changed, 29 insertions(+), 21 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index ca2bcb9..7aa3126 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -1981,6 +1981,21 @@ Instruction *InstCombinerImpl::foldICmpMulConstant(ICmpInst &Cmp, Constant::getNullValue(Mul->getType())); } + // If the multiply does not wrap, try to divide the compare constant by the + // multiplication factor. + if (Cmp.isEquality() && !MulC->isNullValue()) { + // (mul nsw X, MulC) == C --> X == C /s MulC + if (Mul->hasNoSignedWrap() && C.srem(*MulC).isNullValue()) { + Constant *NewC = ConstantInt::get(Mul->getType(), C.sdiv(*MulC)); + return new ICmpInst(Pred, Mul->getOperand(0), NewC); + } + // (mul nuw X, MulC) == C --> X == C /u MulC + if (Mul->hasNoUnsignedWrap() && C.urem(*MulC).isNullValue()) { + Constant *NewC = ConstantInt::get(Mul->getType(), C.udiv(*MulC)); + return new ICmpInst(Pred, Mul->getOperand(0), NewC); + } + } + return nullptr; } @@ -3051,17 +3066,6 @@ Instruction *InstCombinerImpl::foldICmpBinOpEqualityWithConstant( } break; } - case Instruction::Mul: - if (C.isNullValue() && BO->hasNoSignedWrap()) { - const APInt *BOC; - if (match(BOp1, m_APInt(BOC)) && !BOC->isNullValue()) { - // The trivial case (mul X, 0) is handled by InstSimplify. - // General case : (mul X, C) != 0 iff X != 0 - // (mul X, C) == 0 iff X == 0 - return new ICmpInst(Pred, BOp0, Constant::getNullValue(RHS->getType())); - } - } - break; case Instruction::UDiv: if (C.isNullValue()) { // (icmp eq/ne (udiv A, B), 0) -> (icmp ugt/ule i32 B, A) diff --git a/llvm/test/Transforms/InstCombine/icmp-mul.ll b/llvm/test/Transforms/InstCombine/icmp-mul.ll index 45c50c3..8e7d905 100644 --- a/llvm/test/Transforms/InstCombine/icmp-mul.ll +++ b/llvm/test/Transforms/InstCombine/icmp-mul.ll @@ -121,8 +121,7 @@ define i1 @ugt_rem_nz(i8 %x) { define i1 @eq_nsw_rem_zero(i8 %x) { ; CHECK-LABEL: @eq_nsw_rem_zero( -; CHECK-NEXT: [[A:%.*]] = mul nsw i8 [[X:%.*]], -5 -; CHECK-NEXT: [[B:%.*]] = icmp eq i8 [[A]], 20 +; CHECK-NEXT: [[B:%.*]] = icmp eq i8 [[X:%.*]], -4 ; CHECK-NEXT: ret i1 [[B]] ; %a = mul nsw i8 %x, -5 @@ -132,8 +131,7 @@ define i1 @eq_nsw_rem_zero(i8 %x) { define <2 x i1> @ne_nsw_rem_zero(<2 x i8> %x) { ; CHECK-LABEL: @ne_nsw_rem_zero( -; CHECK-NEXT: [[A:%.*]] = mul nsw <2 x i8> [[X:%.*]], -; CHECK-NEXT: [[B:%.*]] = icmp ne <2 x i8> [[A]], +; CHECK-NEXT: [[B:%.*]] = icmp ne <2 x i8> [[X:%.*]], ; CHECK-NEXT: ret <2 x i1> [[B]] ; %a = mul nsw <2 x i8> %x, @@ -141,6 +139,8 @@ define <2 x i1> @ne_nsw_rem_zero(<2 x i8> %x) { ret <2 x i1> %b } +; TODO: Missed fold with undef. + define <2 x i1> @ne_nsw_rem_zero_undef1(<2 x i8> %x) { ; CHECK-LABEL: @ne_nsw_rem_zero_undef1( ; CHECK-NEXT: [[A:%.*]] = mul nsw <2 x i8> [[X:%.*]], @@ -152,6 +152,8 @@ define <2 x i1> @ne_nsw_rem_zero_undef1(<2 x i8> %x) { ret <2 x i1> %b } +; TODO: Missed fold with undef. + define <2 x i1> @ne_nsw_rem_zero_undef2(<2 x i8> %x) { ; CHECK-LABEL: @ne_nsw_rem_zero_undef2( ; CHECK-NEXT: [[A:%.*]] = mul nsw <2 x i8> [[X:%.*]], @@ -167,7 +169,7 @@ define i1 @eq_nsw_rem_zero_uses(i8 %x) { ; CHECK-LABEL: @eq_nsw_rem_zero_uses( ; CHECK-NEXT: [[A:%.*]] = mul nsw i8 [[X:%.*]], -5 ; CHECK-NEXT: call void @use(i8 [[A]]) -; CHECK-NEXT: [[B:%.*]] = icmp eq i8 [[A]], 20 +; CHECK-NEXT: [[B:%.*]] = icmp eq i8 [[X]], -4 ; CHECK-NEXT: ret i1 [[B]] ; %a = mul nsw i8 %x, -5 @@ -200,8 +202,7 @@ define i1 @ne_nsw_rem_nz(i8 %x) { define <2 x i1> @eq_nuw_rem_zero(<2 x i8> %x) { ; CHECK-LABEL: @eq_nuw_rem_zero( -; CHECK-NEXT: [[A:%.*]] = mul nuw <2 x i8> [[X:%.*]], -; CHECK-NEXT: [[B:%.*]] = icmp eq <2 x i8> [[A]], +; CHECK-NEXT: [[B:%.*]] = icmp eq <2 x i8> [[X:%.*]], ; CHECK-NEXT: ret <2 x i1> [[B]] ; %a = mul nuw <2 x i8> %x, @@ -209,6 +210,8 @@ define <2 x i1> @eq_nuw_rem_zero(<2 x i8> %x) { ret <2 x i1> %b } +; TODO: Missed fold with undef. + define <2 x i1> @eq_nuw_rem_zero_undef1(<2 x i8> %x) { ; CHECK-LABEL: @eq_nuw_rem_zero_undef1( ; CHECK-NEXT: [[A:%.*]] = mul nuw <2 x i8> [[X:%.*]], @@ -220,6 +223,8 @@ define <2 x i1> @eq_nuw_rem_zero_undef1(<2 x i8> %x) { ret <2 x i1> %b } +; TODO: Missed fold with undef. + define <2 x i1> @eq_nuw_rem_zero_undef2(<2 x i8> %x) { ; CHECK-LABEL: @eq_nuw_rem_zero_undef2( ; CHECK-NEXT: [[A:%.*]] = mul nuw <2 x i8> [[X:%.*]], @@ -233,8 +238,7 @@ define <2 x i1> @eq_nuw_rem_zero_undef2(<2 x i8> %x) { define i1 @ne_nuw_rem_zero(i8 %x) { ; CHECK-LABEL: @ne_nuw_rem_zero( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 5 -; CHECK-NEXT: [[B:%.*]] = icmp ne i8 [[A]], -126 +; CHECK-NEXT: [[B:%.*]] = icmp ne i8 [[X:%.*]], 26 ; CHECK-NEXT: ret i1 [[B]] ; %a = mul nuw i8 %x, 5 @@ -246,7 +250,7 @@ define i1 @ne_nuw_rem_zero_uses(i8 %x) { ; CHECK-LABEL: @ne_nuw_rem_zero_uses( ; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 5 ; CHECK-NEXT: call void @use(i8 [[A]]) -; CHECK-NEXT: [[B:%.*]] = icmp ne i8 [[A]], -126 +; CHECK-NEXT: [[B:%.*]] = icmp ne i8 [[X]], 26 ; CHECK-NEXT: ret i1 [[B]] ; %a = mul nuw i8 %x, 5 -- 2.7.4