diff options
author | Dimitry Andric <dim@FreeBSD.org> | 2023-12-18 20:30:12 +0000 |
---|---|---|
committer | Dimitry Andric <dim@FreeBSD.org> | 2024-04-06 20:11:55 +0000 |
commit | 5f757f3ff9144b609b3c433dfd370cc6bdc191ad (patch) | |
tree | 1b4e980b866cd26a00af34c0a653eb640bd09caf /contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp | |
parent | 3e1c8a35f741a5d114d0ba670b15191355711fe9 (diff) | |
parent | 312c0ed19cc5276a17bacf2120097bec4515b0f1 (diff) | |
download | src-5f757f3ff9144b609b3c433dfd370cc6bdc191ad.tar.gz src-5f757f3ff9144b609b3c433dfd370cc6bdc191ad.zip |
Merge llvm-project main llvmorg-18-init-15088-gd14ee76181fb
This updates llvm, clang, compiler-rt, libc++, libunwind, lld, lldb and
openmp to llvm-project main llvmorg-18-init-15088-gd14ee76181fb.
PR: 276104
MFC after: 1 month
Diffstat (limited to 'contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp')
-rw-r--r-- | contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp | 135 |
1 files changed, 135 insertions, 0 deletions
diff --git a/contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp b/contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp index e9344a8815c0..cbb64b299e64 100644 --- a/contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp +++ b/contrib/llvm-project/llvm/lib/IR/ConstantRange.cpp @@ -326,6 +326,10 @@ ConstantRange::makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, if (Unsigned) return makeExactMulNUWRegion(Other.getUnsignedMax()); + // Avoid one makeExactMulNSWRegion() call for the common case of constants. + if (const APInt *C = Other.getSingleElement()) + return makeExactMulNSWRegion(*C); + return makeExactMulNSWRegion(Other.getSignedMin()) .intersectWith(makeExactMulNSWRegion(Other.getSignedMax())); @@ -945,6 +949,8 @@ bool ConstantRange::isIntrinsicSupported(Intrinsic::ID IntrinsicID) { case Intrinsic::smax: case Intrinsic::abs: case Intrinsic::ctlz: + case Intrinsic::cttz: + case Intrinsic::ctpop: return true; default: return false; @@ -982,6 +988,14 @@ ConstantRange ConstantRange::intrinsic(Intrinsic::ID IntrinsicID, assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean"); return Ops[0].ctlz(ZeroIsPoison->getBoolValue()); } + case Intrinsic::cttz: { + const APInt *ZeroIsPoison = Ops[1].getSingleElement(); + assert(ZeroIsPoison && "Must be known (immarg)"); + assert(ZeroIsPoison->getBitWidth() == 1 && "Must be boolean"); + return Ops[0].cttz(ZeroIsPoison->getBoolValue()); + } + case Intrinsic::ctpop: + return Ops[0].ctpop(); default: assert(!isIntrinsicSupported(IntrinsicID) && "Shouldn't be supported"); llvm_unreachable("Unsupported intrinsic"); @@ -1477,6 +1491,13 @@ ConstantRange::shl(const ConstantRange &Other) const { } APInt OtherMax = Other.getUnsignedMax(); + if (isAllNegative() && OtherMax.ule(Min.countl_one())) { + // For negative numbers, if the shift does not overflow in a signed sense, + // a larger shift will make the number smaller. + Max <<= Other.getUnsignedMin(); + Min <<= OtherMax; + return ConstantRange::getNonEmpty(std::move(Min), std::move(Max) + 1); + } // There's overflow! if (OtherMax.ugt(Max.countl_zero())) @@ -1725,6 +1746,120 @@ ConstantRange ConstantRange::ctlz(bool ZeroIsPoison) const { APInt(getBitWidth(), getUnsignedMin().countl_zero() + 1)); } +static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower, + const APInt &Upper) { + assert(!ConstantRange(Lower, Upper).isWrappedSet() && + "Unexpected wrapped set."); + assert(Lower != Upper && "Unexpected empty set."); + unsigned BitWidth = Lower.getBitWidth(); + if (Lower + 1 == Upper) + return ConstantRange(APInt(BitWidth, Lower.countr_zero())); + if (Lower.isZero()) + return ConstantRange(APInt::getZero(BitWidth), + APInt(BitWidth, BitWidth + 1)); + + // Calculate longest common prefix. + unsigned LCPLength = (Lower ^ (Upper - 1)).countl_zero(); + // If Lower is {LCP, 000...}, the maximum is Lower.countr_zero(). + // Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}). + return ConstantRange( + APInt::getZero(BitWidth), + APInt(BitWidth, + std::max(BitWidth - LCPLength - 1, Lower.countr_zero()) + 1)); +} + +ConstantRange ConstantRange::cttz(bool ZeroIsPoison) const { + if (isEmptySet()) + return getEmpty(); + + unsigned BitWidth = getBitWidth(); + APInt Zero = APInt::getZero(BitWidth); + if (ZeroIsPoison && contains(Zero)) { + // ZeroIsPoison is set, and zero is contained. We discern three cases, in + // which a zero can appear: + // 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc. + // 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc. + // 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc. + + if (Lower.isZero()) { + if (Upper == 1) { + // We have in input interval of kind [0, 1). In this case we cannot + // really help but return empty-set. + return getEmpty(); + } + + // Compute the resulting range by excluding zero from Lower. + return getUnsignedCountTrailingZerosRange(APInt(BitWidth, 1), Upper); + } else if (Upper == 1) { + // Compute the resulting range by excluding zero from Upper. + return getUnsignedCountTrailingZerosRange(Lower, Zero); + } else { + ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Zero); + ConstantRange CR2 = + getUnsignedCountTrailingZerosRange(APInt(BitWidth, 1), Upper); + return CR1.unionWith(CR2); + } + } + + if (isFullSet()) + return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1)); + if (!isWrappedSet()) + return getUnsignedCountTrailingZerosRange(Lower, Upper); + // The range is wrapped. We decompose it into two ranges, [0, Upper) and + // [Lower, 0). + // Handle [Lower, 0) + ConstantRange CR1 = getUnsignedCountTrailingZerosRange(Lower, Zero); + // Handle [0, Upper) + ConstantRange CR2 = getUnsignedCountTrailingZerosRange(Zero, Upper); + return CR1.unionWith(CR2); +} + +static ConstantRange getUnsignedPopCountRange(const APInt &Lower, + const APInt &Upper) { + assert(!ConstantRange(Lower, Upper).isWrappedSet() && + "Unexpected wrapped set."); + assert(Lower != Upper && "Unexpected empty set."); + unsigned BitWidth = Lower.getBitWidth(); + if (Lower + 1 == Upper) + return ConstantRange(APInt(BitWidth, Lower.popcount())); + + APInt Max = Upper - 1; + // Calculate longest common prefix. + unsigned LCPLength = (Lower ^ Max).countl_zero(); + unsigned LCPPopCount = Lower.getHiBits(LCPLength).popcount(); + // If Lower is {LCP, 000...}, the minimum is the popcount of LCP. + // Otherwise, the minimum is the popcount of LCP + 1. + unsigned MinBits = + LCPPopCount + (Lower.countr_zero() < BitWidth - LCPLength ? 1 : 0); + // If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth - + // length of LCP). + // Otherwise, the minimum is the popcount of LCP + (BitWidth - + // length of LCP - 1). + unsigned MaxBits = LCPPopCount + (BitWidth - LCPLength) - + (Max.countr_one() < BitWidth - LCPLength ? 1 : 0); + return ConstantRange(APInt(BitWidth, MinBits), APInt(BitWidth, MaxBits + 1)); +} + +ConstantRange ConstantRange::ctpop() const { + if (isEmptySet()) + return getEmpty(); + + unsigned BitWidth = getBitWidth(); + APInt Zero = APInt::getZero(BitWidth); + if (isFullSet()) + return getNonEmpty(Zero, APInt(BitWidth, BitWidth + 1)); + if (!isWrappedSet()) + return getUnsignedPopCountRange(Lower, Upper); + // The range is wrapped. We decompose it into two ranges, [0, Upper) and + // [Lower, 0). + // Handle [Lower, 0) == [Lower, Max] + ConstantRange CR1 = ConstantRange(APInt(BitWidth, Lower.countl_one()), + APInt(BitWidth, BitWidth + 1)); + // Handle [0, Upper) + ConstantRange CR2 = getUnsignedPopCountRange(Zero, Upper); + return CR1.unionWith(CR2); +} + ConstantRange::OverflowResult ConstantRange::unsignedAddMayOverflow( const ConstantRange &Other) const { if (isEmptySet() || Other.isEmptySet()) |