From 7a6d6f0f7046f6ebcbf06eaf8f996d991a90e440 Mon Sep 17 00:00:00 2001 From: Sanjay Patel Date: Mon, 7 Sep 2020 12:37:59 -0400 Subject: [PATCH] [InstCombine] improve folds for icmp with multiply operands (PR47432) Check for no overflow along with an odd constant before we lose information by converting to bitwise logic. https://rise4fun.com/Alive/2Xl Pre: C1 != 0 %mx = mul nsw i8 %x, C1 %my = mul nsw i8 %y, C1 %r = icmp eq i8 %mx, %my => %r = icmp eq i8 %x, %y Name: nuw ne Pre: C1 != 0 %mx = mul nuw i8 %x, C1 %my = mul nuw i8 %y, C1 %r = icmp ne i8 %mx, %my => %r = icmp ne i8 %x, %y Name: odd ne Pre: C1 % 2 != 0 %mx = mul i8 %x, C1 %my = mul i8 %y, C1 %r = icmp ne i8 %mx, %my => %r = icmp ne i8 %x, %y --- .../Transforms/InstCombine/InstCombineCompares.cpp | 17 ++++++-- llvm/test/Transforms/InstCombine/icmp-mul.ll | 46 +++++++++------------- 2 files changed, 32 insertions(+), 31 deletions(-) diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp index 350d000..608017b 100644 --- a/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -3983,6 +3983,19 @@ Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I, ConstantExpr::getNeg(RHSC)); } + { + // Try to remove shared constant multiplier from equality comparison: + // X * C == Y * C (with no overflowing/aliasing) --> X == Y + Value *X, *Y; + const APInt *C; + if (match(Op0, m_Mul(m_Value(X), m_APInt(C))) && *C != 0 && + match(Op1, m_Mul(m_Value(Y), m_SpecificInt(*C))) && I.isEquality()) + if (!C->countTrailingZeros() || + (BO0->hasNoSignedWrap() && BO1->hasNoSignedWrap()) || + (BO0->hasNoUnsignedWrap() && BO1->hasNoUnsignedWrap())) + return new ICmpInst(Pred, X, Y); + } + BinaryOperator *SRem = nullptr; // icmp (srem X, Y), Y if (BO0 && BO0->getOpcode() == Instruction::SRem && Op1 == BO0->getOperand(1)) @@ -4059,10 +4072,6 @@ Instruction *InstCombinerImpl::foldICmpBinOp(ICmpInst &I, Value *And2 = Builder.CreateAnd(BO1->getOperand(0), Mask); return new ICmpInst(Pred, And1, And2); } - // If there are no trailing zeros in the multiplier, just eliminate - // the multiplies (no masking is needed): - // icmp eq/ne (X * C), (Y * C) --> icmp eq/ne X, Y - return new ICmpInst(Pred, BO0->getOperand(0), BO1->getOperand(0)); } break; } diff --git a/llvm/test/Transforms/InstCombine/icmp-mul.ll b/llvm/test/Transforms/InstCombine/icmp-mul.ll index 7191500..e2aff1c 100644 --- a/llvm/test/Transforms/InstCombine/icmp-mul.ll +++ b/llvm/test/Transforms/InstCombine/icmp-mul.ll @@ -392,8 +392,7 @@ define i1 @mul_constant_ne_extra_use1(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_ne_extra_use1( ; CHECK-NEXT: [[A:%.*]] = mul i8 [[X:%.*]], 5 ; CHECK-NEXT: call void @use(i8 [[A]]) -; CHECK-NEXT: [[B:%.*]] = mul i8 [[Y:%.*]], 5 -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul i8 %x, 5 @@ -405,10 +404,9 @@ define i1 @mul_constant_ne_extra_use1(i8 %x, i8 %y) { define i1 @mul_constant_eq_extra_use2(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_eq_extra_use2( -; CHECK-NEXT: [[A:%.*]] = mul i8 [[X:%.*]], 5 ; CHECK-NEXT: [[B:%.*]] = mul i8 [[Y:%.*]], 5 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[X:%.*]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul i8 %x, 5 @@ -424,7 +422,7 @@ define i1 @mul_constant_ne_extra_use3(i8 %x, i8 %y) { ; CHECK-NEXT: call void @use(i8 [[A]]) ; CHECK-NEXT: [[B:%.*]] = mul i8 [[Y:%.*]], 5 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul i8 %x, 5 @@ -437,9 +435,7 @@ define i1 @mul_constant_ne_extra_use3(i8 %x, i8 %y) { define i1 @mul_constant_eq_nsw(i32 %x, i32 %y) { ; CHECK-LABEL: @mul_constant_eq_nsw( -; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 2147483647 -; CHECK-NEXT: [[C:%.*]] = icmp eq i32 [[TMP2]], 0 +; CHECK-NEXT: [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nsw i32 %x, 6 @@ -450,9 +446,7 @@ define i1 @mul_constant_eq_nsw(i32 %x, i32 %y) { define <2 x i1> @mul_constant_ne_nsw_splat(<2 x i32> %x, <2 x i32> %y) { ; CHECK-LABEL: @mul_constant_ne_nsw_splat( -; CHECK-NEXT: [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = and <2 x i32> [[TMP1]], -; CHECK-NEXT: [[C:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer +; CHECK-NEXT: [[C:%.*]] = icmp ne <2 x i32> [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret <2 x i1> [[C]] ; %A = mul nsw <2 x i32> %x, @@ -465,8 +459,7 @@ define i1 @mul_constant_ne_nsw_extra_use1(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_ne_nsw_extra_use1( ; CHECK-NEXT: [[A:%.*]] = mul nsw i8 [[X:%.*]], 74 ; CHECK-NEXT: call void @use(i8 [[A]]) -; CHECK-NEXT: [[B:%.*]] = mul nsw i8 [[Y:%.*]], 74 -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nsw i8 %x, 74 @@ -478,10 +471,9 @@ define i1 @mul_constant_ne_nsw_extra_use1(i8 %x, i8 %y) { define i1 @mul_constant_eq_nsw_extra_use2(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_eq_nsw_extra_use2( -; CHECK-NEXT: [[A:%.*]] = mul nsw i8 [[X:%.*]], 20 ; CHECK-NEXT: [[B:%.*]] = mul nsw i8 [[Y:%.*]], 20 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[X:%.*]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nsw i8 %x, 20 @@ -497,7 +489,7 @@ define i1 @mul_constant_ne_nsw_extra_use3(i8 %x, i8 %y) { ; CHECK-NEXT: call void @use(i8 [[A]]) ; CHECK-NEXT: [[B:%.*]] = mul nsw i8 [[Y:%.*]], 24 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nsw i8 %x, 24 @@ -510,9 +502,7 @@ define i1 @mul_constant_ne_nsw_extra_use3(i8 %x, i8 %y) { define i1 @mul_constant_nuw_eq(i32 %x, i32 %y) { ; CHECK-LABEL: @mul_constant_nuw_eq( -; CHECK-NEXT: [[TMP1:%.*]] = xor i32 [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 2147483647 -; CHECK-NEXT: [[C:%.*]] = icmp eq i32 [[TMP2]], 0 +; CHECK-NEXT: [[C:%.*]] = icmp eq i32 [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nuw i32 %x, 22 @@ -523,9 +513,7 @@ define i1 @mul_constant_nuw_eq(i32 %x, i32 %y) { define <2 x i1> @mul_constant_ne_nuw_splat(<2 x i32> %x, <2 x i32> %y) { ; CHECK-LABEL: @mul_constant_ne_nuw_splat( -; CHECK-NEXT: [[TMP1:%.*]] = xor <2 x i32> [[X:%.*]], [[Y:%.*]] -; CHECK-NEXT: [[TMP2:%.*]] = and <2 x i32> [[TMP1]], -; CHECK-NEXT: [[C:%.*]] = icmp ne <2 x i32> [[TMP2]], zeroinitializer +; CHECK-NEXT: [[C:%.*]] = icmp ne <2 x i32> [[X:%.*]], [[Y:%.*]] ; CHECK-NEXT: ret <2 x i1> [[C]] ; %A = mul nuw <2 x i32> %x, @@ -538,8 +526,7 @@ define i1 @mul_constant_ne_nuw_extra_use1(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_ne_nuw_extra_use1( ; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 6 ; CHECK-NEXT: call void @use(i8 [[A]]) -; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Y:%.*]], 6 -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y:%.*]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nuw i8 %x, 6 @@ -551,10 +538,9 @@ define i1 @mul_constant_ne_nuw_extra_use1(i8 %x, i8 %y) { define i1 @mul_constant_eq_nuw_extra_use2(i8 %x, i8 %y) { ; CHECK-LABEL: @mul_constant_eq_nuw_extra_use2( -; CHECK-NEXT: [[A:%.*]] = mul nuw i8 [[X:%.*]], 36 ; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Y:%.*]], 36 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp eq i8 [[X:%.*]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nuw i8 %x, 36 @@ -570,7 +556,7 @@ define i1 @mul_constant_ne_nuw_extra_use3(i8 %x, i8 %y) { ; CHECK-NEXT: call void @use(i8 [[A]]) ; CHECK-NEXT: [[B:%.*]] = mul nuw i8 [[Y:%.*]], 38 ; CHECK-NEXT: call void @use(i8 [[B]]) -; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[A]], [[B]] +; CHECK-NEXT: [[C:%.*]] = icmp ne i8 [[X]], [[Y]] ; CHECK-NEXT: ret i1 [[C]] ; %A = mul nuw i8 %x, 38 @@ -581,6 +567,8 @@ define i1 @mul_constant_ne_nuw_extra_use3(i8 %x, i8 %y) { ret i1 %C } +; Negative test - wrong pred + define i1 @mul_constant_ult(i32 %x, i32 %y) { ; CHECK-LABEL: @mul_constant_ult( ; CHECK-NEXT: [[A:%.*]] = mul i32 [[X:%.*]], 47 @@ -594,6 +582,8 @@ define i1 @mul_constant_ult(i32 %x, i32 %y) { ret i1 %C } +; Negative test - wrong pred + define i1 @mul_constant_nuw_sgt(i32 %x, i32 %y) { ; CHECK-LABEL: @mul_constant_nuw_sgt( ; CHECK-NEXT: [[A:%.*]] = mul nuw i32 [[X:%.*]], 46 @@ -607,6 +597,8 @@ define i1 @mul_constant_nuw_sgt(i32 %x, i32 %y) { ret i1 %C } +; Negative test - wrong constants + define i1 @mul_mismatch_constant_nuw_eq(i32 %x, i32 %y) { ; CHECK-LABEL: @mul_mismatch_constant_nuw_eq( ; CHECK-NEXT: [[A:%.*]] = mul nuw i32 [[X:%.*]], 46 -- 2.7.4