From 490975979bee1a75db06245ea62affc72912fb99 Mon Sep 17 00:00:00 2001 From: Nikita Popov Date: Sat, 9 Mar 2019 21:17:42 +0000 Subject: [PATCH] [ValueTracking] Move constant range computation into ValueTracking; NFC InstructionSimplify currently has some code to determine the constant range of integer instructions for some simple cases. It is used to simplify icmps. This change moves the relevant code into ValueTracking as llvm::computeConstantRange(), so it can also be reused for other purposes. In particular this is with the optimization of overflow checks in mind (ref D59071), where constant ranges cover some cases that known bits don't. llvm-svn: 355781 --- llvm/include/llvm/Analysis/ValueTracking.h | 5 + llvm/lib/Analysis/InstructionSimplify.cpp | 239 +---------------------------- llvm/lib/Analysis/ValueTracking.cpp | 238 ++++++++++++++++++++++++++++ 3 files changed, 244 insertions(+), 238 deletions(-) diff --git a/llvm/include/llvm/Analysis/ValueTracking.h b/llvm/include/llvm/Analysis/ValueTracking.h index b3c07b1..11d2f513 100644 --- a/llvm/include/llvm/Analysis/ValueTracking.h +++ b/llvm/include/llvm/Analysis/ValueTracking.h @@ -460,6 +460,11 @@ class Value; bool isOverflowIntrinsicNoWrap(const IntrinsicInst *II, const DominatorTree &DT); + + /// Determine the possible constant range of an integer or vector of integer + /// value. This is intended as a cheap, non-recursive check. + ConstantRange computeConstantRange(const Value *V, bool UseInstrInfo = true); + /// Return true if this function can prove that the instruction I will /// always transfer execution to one of its successors (including the next /// instruction that follows within a basic block). E.g. this is not diff --git a/llvm/lib/Analysis/InstructionSimplify.cpp b/llvm/lib/Analysis/InstructionSimplify.cpp index baf72a0..047f84f 100644 --- a/llvm/lib/Analysis/InstructionSimplify.cpp +++ b/llvm/lib/Analysis/InstructionSimplify.cpp @@ -2473,228 +2473,6 @@ static Value *simplifyICmpWithZero(CmpInst::Predicate Pred, Value *LHS, return nullptr; } -/// Many binary operators with a constant operand have an easy-to-compute -/// range of outputs. This can be used to fold a comparison to always true or -/// always false. -static void setLimitsForBinOp(BinaryOperator &BO, APInt &Lower, APInt &Upper, - const InstrInfoQuery &IIQ) { - unsigned Width = Lower.getBitWidth(); - const APInt *C; - switch (BO.getOpcode()) { - case Instruction::Add: - if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { - // FIXME: If we have both nuw and nsw, we should reduce the range further. - if (IIQ.hasNoUnsignedWrap(cast(&BO))) { - // 'add nuw x, C' produces [C, UINT_MAX]. - Lower = *C; - } else if (IIQ.hasNoSignedWrap(cast(&BO))) { - if (C->isNegative()) { - // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C]. - Lower = APInt::getSignedMinValue(Width); - Upper = APInt::getSignedMaxValue(Width) + *C + 1; - } else { - // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX]. - Lower = APInt::getSignedMinValue(Width) + *C; - Upper = APInt::getSignedMaxValue(Width) + 1; - } - } - } - break; - - case Instruction::And: - if (match(BO.getOperand(1), m_APInt(C))) - // 'and x, C' produces [0, C]. - Upper = *C + 1; - break; - - case Instruction::Or: - if (match(BO.getOperand(1), m_APInt(C))) - // 'or x, C' produces [C, UINT_MAX]. - Lower = *C; - break; - - case Instruction::AShr: - if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { - // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C]. - Lower = APInt::getSignedMinValue(Width).ashr(*C); - Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1; - } else if (match(BO.getOperand(0), m_APInt(C))) { - unsigned ShiftAmount = Width - 1; - if (!C->isNullValue() && IIQ.isExact(&BO)) - ShiftAmount = C->countTrailingZeros(); - if (C->isNegative()) { - // 'ashr C, x' produces [C, C >> (Width-1)] - Lower = *C; - Upper = C->ashr(ShiftAmount) + 1; - } else { - // 'ashr C, x' produces [C >> (Width-1), C] - Lower = C->ashr(ShiftAmount); - Upper = *C + 1; - } - } - break; - - case Instruction::LShr: - if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { - // 'lshr x, C' produces [0, UINT_MAX >> C]. - Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1; - } else if (match(BO.getOperand(0), m_APInt(C))) { - // 'lshr C, x' produces [C >> (Width-1), C]. - unsigned ShiftAmount = Width - 1; - if (!C->isNullValue() && IIQ.isExact(&BO)) - ShiftAmount = C->countTrailingZeros(); - Lower = C->lshr(ShiftAmount); - Upper = *C + 1; - } - break; - - case Instruction::Shl: - if (match(BO.getOperand(0), m_APInt(C))) { - if (IIQ.hasNoUnsignedWrap(&BO)) { - // 'shl nuw C, x' produces [C, C << CLZ(C)] - Lower = *C; - Upper = Lower.shl(Lower.countLeadingZeros()) + 1; - } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw? - if (C->isNegative()) { - // 'shl nsw C, x' produces [C << CLO(C)-1, C] - unsigned ShiftAmount = C->countLeadingOnes() - 1; - Lower = C->shl(ShiftAmount); - Upper = *C + 1; - } else { - // 'shl nsw C, x' produces [C, C << CLZ(C)-1] - unsigned ShiftAmount = C->countLeadingZeros() - 1; - Lower = *C; - Upper = C->shl(ShiftAmount) + 1; - } - } - } - break; - - case Instruction::SDiv: - if (match(BO.getOperand(1), m_APInt(C))) { - APInt IntMin = APInt::getSignedMinValue(Width); - APInt IntMax = APInt::getSignedMaxValue(Width); - if (C->isAllOnesValue()) { - // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] - // where C != -1 and C != 0 and C != 1 - Lower = IntMin + 1; - Upper = IntMax + 1; - } else if (C->countLeadingZeros() < Width - 1) { - // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C] - // where C != -1 and C != 0 and C != 1 - Lower = IntMin.sdiv(*C); - Upper = IntMax.sdiv(*C); - if (Lower.sgt(Upper)) - std::swap(Lower, Upper); - Upper = Upper + 1; - assert(Upper != Lower && "Upper part of range has wrapped!"); - } - } else if (match(BO.getOperand(0), m_APInt(C))) { - if (C->isMinSignedValue()) { - // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. - Lower = *C; - Upper = Lower.lshr(1) + 1; - } else { - // 'sdiv C, x' produces [-|C|, |C|]. - Upper = C->abs() + 1; - Lower = (-Upper) + 1; - } - } - break; - - case Instruction::UDiv: - if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { - // 'udiv x, C' produces [0, UINT_MAX / C]. - Upper = APInt::getMaxValue(Width).udiv(*C) + 1; - } else if (match(BO.getOperand(0), m_APInt(C))) { - // 'udiv C, x' produces [0, C]. - Upper = *C + 1; - } - break; - - case Instruction::SRem: - if (match(BO.getOperand(1), m_APInt(C))) { - // 'srem x, C' produces (-|C|, |C|). - Upper = C->abs(); - Lower = (-Upper) + 1; - } - break; - - case Instruction::URem: - if (match(BO.getOperand(1), m_APInt(C))) - // 'urem x, C' produces [0, C). - Upper = *C; - break; - - default: - break; - } -} - -/// Some intrinsics with a constant operand have an easy-to-compute range of -/// outputs. This can be used to fold a comparison to always true or always -/// false. -static void setLimitsForIntrinsic(IntrinsicInst &II, APInt &Lower, - APInt &Upper) { - unsigned Width = Lower.getBitWidth(); - const APInt *C; - switch (II.getIntrinsicID()) { - case Intrinsic::uadd_sat: - // uadd.sat(x, C) produces [C, UINT_MAX]. - if (match(II.getOperand(0), m_APInt(C)) || - match(II.getOperand(1), m_APInt(C))) - Lower = *C; - break; - case Intrinsic::sadd_sat: - if (match(II.getOperand(0), m_APInt(C)) || - match(II.getOperand(1), m_APInt(C))) { - if (C->isNegative()) { - // sadd.sat(x, -C) produces [SINT_MIN, SINT_MAX + (-C)]. - Lower = APInt::getSignedMinValue(Width); - Upper = APInt::getSignedMaxValue(Width) + *C + 1; - } else { - // sadd.sat(x, +C) produces [SINT_MIN + C, SINT_MAX]. - Lower = APInt::getSignedMinValue(Width) + *C; - Upper = APInt::getSignedMaxValue(Width) + 1; - } - } - break; - case Intrinsic::usub_sat: - // usub.sat(C, x) produces [0, C]. - if (match(II.getOperand(0), m_APInt(C))) - Upper = *C + 1; - // usub.sat(x, C) produces [0, UINT_MAX - C]. - else if (match(II.getOperand(1), m_APInt(C))) - Upper = APInt::getMaxValue(Width) - *C + 1; - break; - case Intrinsic::ssub_sat: - if (match(II.getOperand(0), m_APInt(C))) { - if (C->isNegative()) { - // ssub.sat(-C, x) produces [SINT_MIN, -SINT_MIN + (-C)]. - Lower = APInt::getSignedMinValue(Width); - Upper = *C - APInt::getSignedMinValue(Width) + 1; - } else { - // ssub.sat(+C, x) produces [-SINT_MAX + C, SINT_MAX]. - Lower = *C - APInt::getSignedMaxValue(Width); - Upper = APInt::getSignedMaxValue(Width) + 1; - } - } else if (match(II.getOperand(1), m_APInt(C))) { - if (C->isNegative()) { - // ssub.sat(x, -C) produces [SINT_MIN - (-C), SINT_MAX]: - Lower = APInt::getSignedMinValue(Width) - *C; - Upper = APInt::getSignedMaxValue(Width) + 1; - } else { - // ssub.sat(x, +C) produces [SINT_MIN, SINT_MAX - C]. - Lower = APInt::getSignedMinValue(Width); - Upper = APInt::getSignedMaxValue(Width) - *C + 1; - } - } - break; - default: - break; - } -} - static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const InstrInfoQuery &IIQ) { Type *ITy = GetCompareTy(RHS); // The return type. @@ -2722,22 +2500,7 @@ static Value *simplifyICmpWithConstant(CmpInst::Predicate Pred, Value *LHS, if (RHS_CR.isFullSet()) return ConstantInt::getTrue(ITy); - // Find the range of possible values for binary operators. - unsigned Width = C->getBitWidth(); - APInt Lower = APInt(Width, 0); - APInt Upper = APInt(Width, 0); - if (auto *BO = dyn_cast(LHS)) - setLimitsForBinOp(*BO, Lower, Upper, IIQ); - else if (auto *II = dyn_cast(LHS)) - setLimitsForIntrinsic(*II, Lower, Upper); - - ConstantRange LHS_CR = - Lower != Upper ? ConstantRange(Lower, Upper) : ConstantRange(Width, true); - - if (auto *I = dyn_cast(LHS)) - if (auto *Ranges = IIQ.getMetadata(I, LLVMContext::MD_range)) - LHS_CR = LHS_CR.intersectWith(getConstantRangeFromMetadata(*Ranges)); - + ConstantRange LHS_CR = computeConstantRange(LHS, IIQ.UseInstrInfo); if (!LHS_CR.isFullSet()) { if (RHS_CR.contains(LHS_CR)) return ConstantInt::getTrue(ITy); diff --git a/llvm/lib/Analysis/ValueTracking.cpp b/llvm/lib/Analysis/ValueTracking.cpp index 64250f6..ac68689 100644 --- a/llvm/lib/Analysis/ValueTracking.cpp +++ b/llvm/lib/Analysis/ValueTracking.cpp @@ -5473,3 +5473,241 @@ Optional llvm::isImpliedByDomCondition(const Value *Cond, bool CondIsTrue = TrueBB == ContextBB; return isImpliedCondition(PredCond, Cond, DL, CondIsTrue); } + +static void setLimitsForBinOp(const BinaryOperator &BO, APInt &Lower, + APInt &Upper, const InstrInfoQuery &IIQ) { + unsigned Width = Lower.getBitWidth(); + const APInt *C; + switch (BO.getOpcode()) { + case Instruction::Add: + if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { + // FIXME: If we have both nuw and nsw, we should reduce the range further. + if (IIQ.hasNoUnsignedWrap(cast(&BO))) { + // 'add nuw x, C' produces [C, UINT_MAX]. + Lower = *C; + } else if (IIQ.hasNoSignedWrap(cast(&BO))) { + if (C->isNegative()) { + // 'add nsw x, -C' produces [SINT_MIN, SINT_MAX - C]. + Lower = APInt::getSignedMinValue(Width); + Upper = APInt::getSignedMaxValue(Width) + *C + 1; + } else { + // 'add nsw x, +C' produces [SINT_MIN + C, SINT_MAX]. + Lower = APInt::getSignedMinValue(Width) + *C; + Upper = APInt::getSignedMaxValue(Width) + 1; + } + } + } + break; + + case Instruction::And: + if (match(BO.getOperand(1), m_APInt(C))) + // 'and x, C' produces [0, C]. + Upper = *C + 1; + break; + + case Instruction::Or: + if (match(BO.getOperand(1), m_APInt(C))) + // 'or x, C' produces [C, UINT_MAX]. + Lower = *C; + break; + + case Instruction::AShr: + if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { + // 'ashr x, C' produces [INT_MIN >> C, INT_MAX >> C]. + Lower = APInt::getSignedMinValue(Width).ashr(*C); + Upper = APInt::getSignedMaxValue(Width).ashr(*C) + 1; + } else if (match(BO.getOperand(0), m_APInt(C))) { + unsigned ShiftAmount = Width - 1; + if (!C->isNullValue() && IIQ.isExact(&BO)) + ShiftAmount = C->countTrailingZeros(); + if (C->isNegative()) { + // 'ashr C, x' produces [C, C >> (Width-1)] + Lower = *C; + Upper = C->ashr(ShiftAmount) + 1; + } else { + // 'ashr C, x' produces [C >> (Width-1), C] + Lower = C->ashr(ShiftAmount); + Upper = *C + 1; + } + } + break; + + case Instruction::LShr: + if (match(BO.getOperand(1), m_APInt(C)) && C->ult(Width)) { + // 'lshr x, C' produces [0, UINT_MAX >> C]. + Upper = APInt::getAllOnesValue(Width).lshr(*C) + 1; + } else if (match(BO.getOperand(0), m_APInt(C))) { + // 'lshr C, x' produces [C >> (Width-1), C]. + unsigned ShiftAmount = Width - 1; + if (!C->isNullValue() && IIQ.isExact(&BO)) + ShiftAmount = C->countTrailingZeros(); + Lower = C->lshr(ShiftAmount); + Upper = *C + 1; + } + break; + + case Instruction::Shl: + if (match(BO.getOperand(0), m_APInt(C))) { + if (IIQ.hasNoUnsignedWrap(&BO)) { + // 'shl nuw C, x' produces [C, C << CLZ(C)] + Lower = *C; + Upper = Lower.shl(Lower.countLeadingZeros()) + 1; + } else if (BO.hasNoSignedWrap()) { // TODO: What if both nuw+nsw? + if (C->isNegative()) { + // 'shl nsw C, x' produces [C << CLO(C)-1, C] + unsigned ShiftAmount = C->countLeadingOnes() - 1; + Lower = C->shl(ShiftAmount); + Upper = *C + 1; + } else { + // 'shl nsw C, x' produces [C, C << CLZ(C)-1] + unsigned ShiftAmount = C->countLeadingZeros() - 1; + Lower = *C; + Upper = C->shl(ShiftAmount) + 1; + } + } + } + break; + + case Instruction::SDiv: + if (match(BO.getOperand(1), m_APInt(C))) { + APInt IntMin = APInt::getSignedMinValue(Width); + APInt IntMax = APInt::getSignedMaxValue(Width); + if (C->isAllOnesValue()) { + // 'sdiv x, -1' produces [INT_MIN + 1, INT_MAX] + // where C != -1 and C != 0 and C != 1 + Lower = IntMin + 1; + Upper = IntMax + 1; + } else if (C->countLeadingZeros() < Width - 1) { + // 'sdiv x, C' produces [INT_MIN / C, INT_MAX / C] + // where C != -1 and C != 0 and C != 1 + Lower = IntMin.sdiv(*C); + Upper = IntMax.sdiv(*C); + if (Lower.sgt(Upper)) + std::swap(Lower, Upper); + Upper = Upper + 1; + assert(Upper != Lower && "Upper part of range has wrapped!"); + } + } else if (match(BO.getOperand(0), m_APInt(C))) { + if (C->isMinSignedValue()) { + // 'sdiv INT_MIN, x' produces [INT_MIN, INT_MIN / -2]. + Lower = *C; + Upper = Lower.lshr(1) + 1; + } else { + // 'sdiv C, x' produces [-|C|, |C|]. + Upper = C->abs() + 1; + Lower = (-Upper) + 1; + } + } + break; + + case Instruction::UDiv: + if (match(BO.getOperand(1), m_APInt(C)) && !C->isNullValue()) { + // 'udiv x, C' produces [0, UINT_MAX / C]. + Upper = APInt::getMaxValue(Width).udiv(*C) + 1; + } else if (match(BO.getOperand(0), m_APInt(C))) { + // 'udiv C, x' produces [0, C]. + Upper = *C + 1; + } + break; + + case Instruction::SRem: + if (match(BO.getOperand(1), m_APInt(C))) { + // 'srem x, C' produces (-|C|, |C|). + Upper = C->abs(); + Lower = (-Upper) + 1; + } + break; + + case Instruction::URem: + if (match(BO.getOperand(1), m_APInt(C))) + // 'urem x, C' produces [0, C). + Upper = *C; + break; + + default: + break; + } +} + +static void setLimitsForIntrinsic(const IntrinsicInst &II, APInt &Lower, + APInt &Upper) { + unsigned Width = Lower.getBitWidth(); + const APInt *C; + switch (II.getIntrinsicID()) { + case Intrinsic::uadd_sat: + // uadd.sat(x, C) produces [C, UINT_MAX]. + if (match(II.getOperand(0), m_APInt(C)) || + match(II.getOperand(1), m_APInt(C))) + Lower = *C; + break; + case Intrinsic::sadd_sat: + if (match(II.getOperand(0), m_APInt(C)) || + match(II.getOperand(1), m_APInt(C))) { + if (C->isNegative()) { + // sadd.sat(x, -C) produces [SINT_MIN, SINT_MAX + (-C)]. + Lower = APInt::getSignedMinValue(Width); + Upper = APInt::getSignedMaxValue(Width) + *C + 1; + } else { + // sadd.sat(x, +C) produces [SINT_MIN + C, SINT_MAX]. + Lower = APInt::getSignedMinValue(Width) + *C; + Upper = APInt::getSignedMaxValue(Width) + 1; + } + } + break; + case Intrinsic::usub_sat: + // usub.sat(C, x) produces [0, C]. + if (match(II.getOperand(0), m_APInt(C))) + Upper = *C + 1; + // usub.sat(x, C) produces [0, UINT_MAX - C]. + else if (match(II.getOperand(1), m_APInt(C))) + Upper = APInt::getMaxValue(Width) - *C + 1; + break; + case Intrinsic::ssub_sat: + if (match(II.getOperand(0), m_APInt(C))) { + if (C->isNegative()) { + // ssub.sat(-C, x) produces [SINT_MIN, -SINT_MIN + (-C)]. + Lower = APInt::getSignedMinValue(Width); + Upper = *C - APInt::getSignedMinValue(Width) + 1; + } else { + // ssub.sat(+C, x) produces [-SINT_MAX + C, SINT_MAX]. + Lower = *C - APInt::getSignedMaxValue(Width); + Upper = APInt::getSignedMaxValue(Width) + 1; + } + } else if (match(II.getOperand(1), m_APInt(C))) { + if (C->isNegative()) { + // ssub.sat(x, -C) produces [SINT_MIN - (-C), SINT_MAX]: + Lower = APInt::getSignedMinValue(Width) - *C; + Upper = APInt::getSignedMaxValue(Width) + 1; + } else { + // ssub.sat(x, +C) produces [SINT_MIN, SINT_MAX - C]. + Lower = APInt::getSignedMinValue(Width); + Upper = APInt::getSignedMaxValue(Width) - *C + 1; + } + } + break; + default: + break; + } +} + +ConstantRange llvm::computeConstantRange(const Value *V, bool UseInstrInfo) { + assert(V->getType()->isIntOrIntVectorTy() && "Expected integer instruction"); + + InstrInfoQuery IIQ(UseInstrInfo); + unsigned BitWidth = V->getType()->getScalarSizeInBits(); + APInt Lower = APInt(BitWidth, 0); + APInt Upper = APInt(BitWidth, 0); + if (auto *BO = dyn_cast(V)) + setLimitsForBinOp(*BO, Lower, Upper, IIQ); + else if (auto *II = dyn_cast(V)) + setLimitsForIntrinsic(*II, Lower, Upper); + + ConstantRange CR = Lower != Upper ? ConstantRange(Lower, Upper) + : ConstantRange(BitWidth, true); + + if (auto *I = dyn_cast(V)) + if (auto *Range = IIQ.getMetadata(I, LLVMContext::MD_range)) + CR = CR.intersectWith(getConstantRangeFromMetadata(*Range)); + + return CR; +} -- 2.7.4