From: Arnaud A. de Grandmaison Date: Mon, 25 Mar 2013 09:48:49 +0000 (+0000) Subject: InstCombine: simplify comparisons to zero of (shl %x, Cst) or (mul %x, Cst) X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=commitdiff_plain;h=35763b1ee700cd29f057494a35095f06d983fe6e InstCombine: simplify comparisons to zero of (shl %x, Cst) or (mul %x, Cst) This simplification happens at 2 places : - using the nsw attribute when the shl / mul is used by a sign test - when the shl / mul is compared for (in)equality to zero git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@177856 91177308-0d34-0410-b5e6-96231b3b80d8 --- diff --git a/lib/Transforms/InstCombine/InstCombineCompares.cpp b/lib/Transforms/InstCombine/InstCombineCompares.cpp index a4e117e4c4b..24af2bfaf52 100644 --- a/lib/Transforms/InstCombine/InstCombineCompares.cpp +++ b/lib/Transforms/InstCombine/InstCombineCompares.cpp @@ -139,6 +139,42 @@ static bool isSignBitCheck(ICmpInst::Predicate pred, ConstantInt *RHS, } } +/// Returns true if the exploded icmp can be expressed as a comparison to zero +/// and update the predicate accordingly. The signedness of the comparison is +static bool isSignTest(ICmpInst::Predicate &pred, const ConstantInt *RHS) { + if (!ICmpInst::isSigned(pred)) + return false; + + if (RHS->isZero()) + return true; + + if (RHS->isOne()) + switch (pred) { + case ICmpInst::ICMP_SGE: + pred = ICmpInst::ICMP_SGT; + return true; + case ICmpInst::ICMP_SLT: + pred = ICmpInst::ICMP_SLE; + return true; + default: + return false; + } + + if (RHS->isAllOnesValue()) + switch (pred) { + case ICmpInst::ICMP_SLE: + pred = ICmpInst::ICMP_SLT; + return true; + case ICmpInst::ICMP_SGT: + pred = ICmpInst::ICMP_SGE; + return true; + default: + return false; + } + + return false; +} + // isHighOnes - Return true if the constant is of the form 1+0+. // This is the same as lowones(~X). static bool isHighOnes(const ConstantInt *CI) { @@ -1282,6 +1318,25 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, break; } + case Instruction::Mul: { // (icmp pred (mul X, Val), CI) + ConstantInt *Val = dyn_cast(LHSI->getOperand(1)); + if (!Val) break; + + if (!ICI.isEquality()) { + // If this is a signed comparison to 0 and the mul is sign preserving, + // use the mul LHS operand instead. + ICmpInst::Predicate pred = ICI.getPredicate(); + if (isSignTest(pred, RHS) && !Val->isZero() && + cast(LHSI)->hasNoSignedWrap()) + return new ICmpInst(Val->isNegative() ? + ICmpInst::getSwappedPredicate(pred) : pred, + LHSI->getOperand(0), + Constant::getNullValue(RHS->getType())); + } + + break; + } + case Instruction::Shl: { // (icmp pred (shl X, ShAmt), CI) ConstantInt *ShAmt = dyn_cast(LHSI->getOperand(1)); if (!ShAmt) break; @@ -1313,6 +1368,12 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0), ConstantExpr::getLShr(RHS, ShAmt)); + // If the shift is NSW and we compare to 0, then it is just shifting out + // sign bits, no need for an AND either. + if (cast(LHSI)->hasNoSignedWrap() && RHSV == 0) + return new ICmpInst(ICI.getPredicate(), LHSI->getOperand(0), + ConstantExpr::getLShr(RHS, ShAmt)); + if (LHSI->hasOneUse()) { // Otherwise strength reduce the shift into an and. uint32_t ShAmtVal = (uint32_t)ShAmt->getLimitedValue(TypeBits); @@ -1327,6 +1388,15 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, } } + // If this is a signed comparison to 0 and the shift is sign preserving, + // use the shift LHS operand instead. + ICmpInst::Predicate pred = ICI.getPredicate(); + if (isSignTest(pred, RHS) && + cast(LHSI)->hasNoSignedWrap()) + return new ICmpInst(pred, + LHSI->getOperand(0), + Constant::getNullValue(RHS->getType())); + // Otherwise, if this is a comparison of the sign bit, simplify to and/test. bool TrueIfSigned = false; if (LHSI->hasOneUse() && @@ -1541,6 +1611,19 @@ Instruction *InstCombiner::visitICmpInstWithInstAndIntCst(ICmpInst &ICI, return new ICmpInst(pred, X, NegX); } } + break; + case Instruction::Mul: + if (RHSV == 0) { + if (ConstantInt *BOC = dyn_cast(BO->getOperand(1))) { + // 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 + if (!BOC->isZero()) + return new ICmpInst(ICI.getPredicate(), BO->getOperand(0), + Constant::getNullValue(RHS->getType())); + } + } + break; default: break; } } else if (IntrinsicInst *II = dyn_cast(LHSI)) { diff --git a/test/Transforms/InstCombine/icmp.ll b/test/Transforms/InstCombine/icmp.ll index 331eb3f21a9..2bfdb5c70bb 100644 --- a/test/Transforms/InstCombine/icmp.ll +++ b/test/Transforms/InstCombine/icmp.ll @@ -744,3 +744,145 @@ define i1 @icmp_shl24(i32 %x) { %cmp = icmp slt i32 %shl, 603979776 ret i1 %cmp } + +; If the (shl x, C) preserved the sign and this is a sign test, +; compare the LHS operand instead +; CHECK: @icmp_shl_nsw_sgt +; CHECK-NEXT: icmp sgt i32 %x, 0 +define i1 @icmp_shl_nsw_sgt(i32 %x) { + %shl = shl nsw i32 %x, 21 + %cmp = icmp sgt i32 %shl, 0 + ret i1 %cmp +} + +; CHECK: @icmp_shl_nsw_sge0 +; CHECK-NEXT: icmp sgt i32 %x, -1 +define i1 @icmp_shl_nsw_sge0(i32 %x) { + %shl = shl nsw i32 %x, 21 + %cmp = icmp sge i32 %shl, 0 + ret i1 %cmp +} + +; CHECK: @icmp_shl_nsw_sge1 +; CHECK-NEXT: icmp sgt i32 %x, 0 +define i1 @icmp_shl_nsw_sge1(i32 %x) { + %shl = shl nsw i32 %x, 21 + %cmp = icmp sge i32 %shl, 1 + ret i1 %cmp +} + +; Checks for icmp (eq|ne) (shl x, C), 0 +; CHECK: @icmp_shl_nsw_eq +; CHECK-NEXT: icmp eq i32 %x, 0 +define i1 @icmp_shl_nsw_eq(i32 %x) { + %mul = shl nsw i32 %x, 5 + %cmp = icmp eq i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_shl_eq +; CHECK-NOT: icmp eq i32 %mul, 0 +define i1 @icmp_shl_eq(i32 %x) { + %mul = shl i32 %x, 5 + %cmp = icmp eq i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_shl_nsw_ne +; CHECK-NEXT: icmp ne i32 %x, 0 +define i1 @icmp_shl_nsw_ne(i32 %x) { + %mul = shl nsw i32 %x, 7 + %cmp = icmp ne i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_shl_ne +; CHECK-NOT: icmp ne i32 %x, 0 +define i1 @icmp_shl_ne(i32 %x) { + %mul = shl i32 %x, 7 + %cmp = icmp ne i32 %mul, 0 + ret i1 %cmp +} + +; If the (mul x, C) preserved the sign and this is sign test, +; compare the LHS operand instead +; CHECK: @icmp_mul_nsw +; CHECK-NEXT: icmp sgt i32 %x, 0 +define i1 @icmp_mul_nsw(i32 %x) { + %mul = mul nsw i32 %x, 12 + %cmp = icmp sgt i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul_nsw1 +; CHECK-NEXT: icmp slt i32 %x, 0 +define i1 @icmp_mul_nsw1(i32 %x) { + %mul = mul nsw i32 %x, 12 + %cmp = icmp sle i32 %mul, -1 + ret i1 %cmp +} + +; CHECK: @icmp_mul_nsw_neg +; CHECK-NEXT: icmp slt i32 %x, 1 +define i1 @icmp_mul_nsw_neg(i32 %x) { + %mul = mul nsw i32 %x, -12 + %cmp = icmp sge i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul_nsw_neg1 +; CHECK-NEXT: icmp slt i32 %x, 0 +define i1 @icmp_mul_nsw_neg1(i32 %x) { + %mul = mul nsw i32 %x, -12 + %cmp = icmp sge i32 %mul, 1 + ret i1 %cmp +} + +; CHECK: @icmp_mul_nsw_0 +; CHECK-NOT: icmp sgt i32 %x, 0 +define i1 @icmp_mul_nsw_0(i32 %x) { + %mul = mul nsw i32 %x, 0 + %cmp = icmp sgt i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul +; CHECK-NEXT: %mul = mul i32 %x, -12 +define i1 @icmp_mul(i32 %x) { + %mul = mul i32 %x, -12 + %cmp = icmp sge i32 %mul, 0 + ret i1 %cmp +} + +; Checks for icmp (eq|ne) (mul x, C), 0 +; CHECK: @icmp_mul_neq0 +; CHECK-NEXT: icmp ne i32 %x, 0 +define i1 @icmp_mul_neq0(i32 %x) { + %mul = mul i32 %x, -12 + %cmp = icmp ne i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul_eq0 +; CHECK-NEXT: icmp eq i32 %x, 0 +define i1 @icmp_mul_eq0(i32 %x) { + %mul = mul i32 %x, 12 + %cmp = icmp eq i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul0_eq0 +; CHECK-NEXT: ret i1 true +define i1 @icmp_mul0_eq0(i32 %x) { + %mul = mul i32 %x, 0 + %cmp = icmp eq i32 %mul, 0 + ret i1 %cmp +} + +; CHECK: @icmp_mul0_ne0 +; CHECK-NEXT: ret i1 false +define i1 @icmp_mul0_ne0(i32 %x) { + %mul = mul i32 %x, 0 + %cmp = icmp ne i32 %mul, 0 + ret i1 %cmp +}