1//===- ConstantRange.cpp - ConstantRange implementation -------------------===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// Represent a range of possible values that may occur when the program is run 10// for an integral value. This keeps track of a lower and upper bound for the 11// constant, which MAY wrap around the end of the numeric range. To do this, it 12// keeps track of a [lower, upper) bound, which specifies an interval just like 13// STL iterators. When used with boolean values, the following are important 14// ranges (other integral ranges use min/max values for special range values): 16// [F, F) = {} = Empty set 19// [T, T) = {F, T} = Full set 21//===----------------------------------------------------------------------===// 25#include "llvm/Config/llvm-config.h" 55"ConstantRange with unequal bit widths");
57"Lower == Upper, but they aren't min or max value!");
67// For unsigned ranges, or signed ranges with known sign bit, create a simple 68// range between the smallest and largest possible value. 72// If we don't know the sign bit, pick the lower bound as a negative number 73// and the upper bound as a non-negative one. 81// TODO: We could return conflicting known bits here, but consumers are 82// likely not prepared for that. 86// We can only retain the top bits that are the same between min and max. 90if (std::optional<unsigned> DifferentBit =
115if (
UMax.isMinValue())
121if (
SMax.isMinSignedValue())
131if (
UMin.isMaxValue())
137if (
SMin.isMaxSignedValue())
150// Follows from De-Morgan's laws: 152// ~(~A union ~B) == A intersect B. 160// Computes the exact range that is equal to both the constant ranges returned 161// by makeAllowedICmpRegion and makeSatisfyingICmpRegion. This is always true 162// when RHS is a singleton such as an APInt and so the assert is valid. 163// However for non-singleton RHS, for example ult [2,5) makeAllowedICmpRegion 164// returns [0,4) but makeSatisfyICmpRegion returns [0,2). 192"Only for relational integer predicates!");
198return FlippedSignednessPred;
217RHS = *OnlyMissingElt;
277/// Exact mul nuw region for single element RHS. 281return ConstantRange::getFull(V.getBitWidth());
290/// Exact mul nsw region for single element RHS. 292// Handle 0 and -1 separately to avoid division by zero or overflow. 295return ConstantRange::getFull(
BitWidth);
299// e.g. Returning [-127, 127], represented as [-127, -128). 317unsigned NoWrapKind) {
322assert((NoWrapKind == OBO::NoSignedWrap ||
323 NoWrapKind == OBO::NoUnsignedWrap) &&
324"NoWrapKind invalid!");
326boolUnsigned = NoWrapKind == OBO::NoUnsignedWrap;
333case Instruction::Add: {
340SMin.isNegative() ? SignedMinVal -
SMin : SignedMinVal,
341SMax.isStrictlyPositive() ? SignedMinVal -
SMax : SignedMinVal);
344case Instruction::Sub: {
351SMax.isStrictlyPositive() ? SignedMinVal +
SMax : SignedMinVal,
352SMin.isNegative() ? SignedMinVal +
SMin : SignedMinVal);
355case Instruction::Mul:
359// Avoid one makeExactMulNSWRegion() call for the common case of constants. 366case Instruction::Shl: {
367// For given range of shift amounts, if we ignore all illegal shift amounts 368// (that always produce poison), what shift amount range is left? 372// If the entire range of shift amounts is already poison-producing, 373// then we can freely add more poison-producing flags ontop of that. 376// There are some legal shift amounts, we can compute conservatively-correct 377// range of no-wrap inputs. Note that by now we have clamped the ShAmtUMax 378// to be at most bitwidth-1, which results in most conservative range. 391unsigned NoWrapKind) {
392// makeGuaranteedNoWrapRegion() is exact for single-element ranges, as 393// "for all" and "for any" coincide in this case. 399unsignedBitWidth = Mask.getBitWidth();
407// If (Val & Mask) != C, constrained to the non-equality being 408// satisfiable, then the value must be larger than the lowest set bit of 409// Mask, offset by constant C. 423return Lower.
ugt(Upper) && !Upper.
isZero();
427return Lower.
ugt(Upper);
435return Lower.
sgt(Upper);
443if (
Other.isFullSet())
445return (Upper - Lower).ult(
Other.Upper -
Other.Lower);
450// If this a full set, we need special handling to avoid needing an extra bit 451// to represent the size. 455return (Upper - Lower).ugt(MaxSize);
459// Empty set is all negative, full set is not. 469// Empty and full set are automatically treated correctly. 474// Empty set is all positive, full set is not. 512return Lower.
ule(V) && V.ult(Upper);
513return Lower.
ule(V) || V.ult(Upper);
521if (
Other.isUpperWrapped())
524return Lower.
ule(
Other.getLower()) &&
Other.getUpper().ule(Upper);
527if (!
Other.isUpperWrapped())
528returnOther.getUpper().ule(Upper) ||
531returnOther.getUpper().ule(Upper) && Lower.
ule(
Other.getLower());
551// If the set is empty or full, don't modify the endpoints. 584"ConstantRange types don't agree!");
586// Handle common cases. 594if (Lower.
ult(CR.Lower)) {
597if (Upper.
ule(CR.Lower))
602if (Upper.
ult(CR.Upper))
611if (Upper.
ult(CR.Upper))
616if (Lower.
ult(CR.Upper))
625if (CR.Lower.
ult(Upper)) {
626// ------U L--- : this 628if (CR.Upper.
ult(Upper))
631// ------U L--- : this 633if (CR.Upper.
ule(Lower))
636// ------U L--- : this 640if (CR.Lower.
ult(Lower)) {
643if (CR.Upper.
ule(Lower))
656if (CR.Upper.
ult(Upper)) {
659if (CR.Lower.
ult(Upper))
664if (CR.Lower.
ult(Lower))
671if (CR.Upper.
ule(Lower)) {
674if (CR.Lower.
ult(Lower))
690"ConstantRange types don't agree!");
699// L---U and L---U : this 704if (CR.Upper.
ult(Lower) || Upper.
ult(CR.Lower))
708APInt L = CR.Lower.
ult(Lower) ? CR.Lower : Lower;
709APInt U = (CR.Upper - 1).ugt(Upper - 1) ? CR.Upper : Upper;
711if (L.isZero() && U.isZero())
718// ------U L----- and ------U L----- : this 720if (CR.Upper.
ule(Upper) || CR.Lower.
uge(Lower))
723// ------U L----- : this 725if (CR.Lower.
ule(Upper) && Lower.
ule(CR.Upper))
733if (Upper.
ult(CR.Lower) && CR.Upper.
ult(Lower))
737// ----U L----- : this 739if (Upper.
ult(CR.Lower) && Lower.
ule(CR.Upper))
742// ------U L---- : this 745"ConstantRange::unionWith missed a case with one range wrapped");
749// ------U L---- and ------U L---- : this 750// -U L----------- and ------------U L : CR 751if (CR.Lower.
ule(Upper) || Lower.
ule(CR.Upper))
754APInt L = CR.Lower.
ult(Lower) ? CR.Lower : Lower;
755APInt U = CR.Upper.
ugt(Upper) ? CR.Upper : Upper;
760std::optional<ConstantRange>
762// TODO: This can be implemented more efficiently. 769std::optional<ConstantRange>
771// TODO: This can be implemented more efficiently. 783case Instruction::Trunc:
785case Instruction::SExt:
787case Instruction::ZExt:
789case Instruction::BitCast:
791case Instruction::FPToUI:
792case Instruction::FPToSI:
796return getFull(ResultBitWidth);
797case Instruction::UIToFP: {
798// TODO: use input range if available 802if (ResultBitWidth > BW) {
803 Min = Min.
zext(ResultBitWidth);
804 Max = Max.zext(ResultBitWidth);
806returngetNonEmpty(std::move(Min), std::move(Max) + 1);
808case Instruction::SIToFP: {
809// TODO: use input range if available 813if (ResultBitWidth > BW) {
819case Instruction::FPTrunc:
820case Instruction::FPExt:
821case Instruction::IntToPtr:
822case Instruction::PtrToInt:
823case Instruction::AddrSpaceCast:
824// Conservatively return getFull set. 825return getFull(ResultBitWidth);
833assert(SrcTySize < DstTySize &&
"Not a value extension");
835// Change into [0, 1 << src bit width) 836APInt LowerExt(DstTySize, 0);
837if (!Upper)
// special case: [X, 0) -- not really wrapping around 838 LowerExt = Lower.
zext(DstTySize);
850assert(SrcTySize < DstTySize &&
"Not a value extension");
852// special case: [X, INT_MIN) -- not really wrapping around 867return getEmpty(DstTySize);
869return getFull(DstTySize);
871APInt LowerDiv(Lower), UpperDiv(Upper);
874// Analyze wrapped sets in their two parts: [0, Upper) \/ [Lower, MaxValue] 875// We use the non-wrapped set code to analyze the [Lower, MaxValue) part, and 876// then we do the union with [MaxValue, Upper) 878// If Upper is greater than or equal to MaxValue(DstTy), it covers the whole 881return getFull(DstTySize);
886// Union covers the MaxValue case, so return if the remaining range is just 888if (LowerDiv == UpperDiv)
892// Chop off the most significant bits that are past the destination bitwidth. 893if (LowerDiv.getActiveBits() > DstTySize) {
894// Mask to just the signficant bits and subtract from LowerDiv/UpperDiv. 901if (UpperDivWidth <= DstTySize)
905// The truncated value wraps around. Check if we can do better than fullset. 906if (UpperDivWidth == DstTySize + 1) {
907// Clear the MSB so that UpperDiv wraps around. 909if (UpperDiv.
ult(LowerDiv))
914return getFull(DstTySize);
919if (SrcTySize > DstTySize)
921if (SrcTySize < DstTySize)
928if (SrcTySize > DstTySize)
930if (SrcTySize < DstTySize)
940case Instruction::Add:
942case Instruction::Sub:
944case Instruction::Mul:
946case Instruction::UDiv:
948case Instruction::SDiv:
950case Instruction::URem:
952case Instruction::SRem:
954case Instruction::Shl:
956case Instruction::LShr:
958case Instruction::AShr:
960case Instruction::And:
964case Instruction::Xor:
966// Note: floating point operations applied to abstract ranges are just 967// ideal integer operations with a lossy representation 968case Instruction::FAdd:
970case Instruction::FSub:
972case Instruction::FMul:
975// Conservatively return getFull set. 982unsigned NoWrapKind)
const{
986case Instruction::Add:
988case Instruction::Sub:
990case Instruction::Mul:
992case Instruction::Shl:
995// Don't know about this Overflowing Binary Operation. 996// Conservatively fallback to plain binop handling. 1002switch (IntrinsicID) {
1003case Intrinsic::uadd_sat:
1004case Intrinsic::usub_sat:
1005case Intrinsic::sadd_sat:
1006case Intrinsic::ssub_sat:
1007case Intrinsic::umin:
1008case Intrinsic::umax:
1009case Intrinsic::smin:
1010case Intrinsic::smax:
1012case Intrinsic::ctlz:
1013case Intrinsic::cttz:
1014case Intrinsic::ctpop:
1023switch (IntrinsicID) {
1024case Intrinsic::uadd_sat:
1025return Ops[0].uadd_sat(Ops[1]);
1026case Intrinsic::usub_sat:
1027return Ops[0].usub_sat(Ops[1]);
1028case Intrinsic::sadd_sat:
1029return Ops[0].sadd_sat(Ops[1]);
1030case Intrinsic::ssub_sat:
1031return Ops[0].ssub_sat(Ops[1]);
1032case Intrinsic::umin:
1033return Ops[0].umin(Ops[1]);
1034case Intrinsic::umax:
1035return Ops[0].umax(Ops[1]);
1036case Intrinsic::smin:
1037return Ops[0].smin(Ops[1]);
1038case Intrinsic::smax:
1039return Ops[0].smax(Ops[1]);
1040case Intrinsic::abs: {
1041constAPInt *IntMinIsPoison = Ops[1].getSingleElement();
1042assert(IntMinIsPoison &&
"Must be known (immarg)");
1046case Intrinsic::ctlz: {
1047constAPInt *ZeroIsPoison = Ops[1].getSingleElement();
1048assert(ZeroIsPoison &&
"Must be known (immarg)");
1052case Intrinsic::cttz: {
1053constAPInt *ZeroIsPoison = Ops[1].getSingleElement();
1054assert(ZeroIsPoison &&
"Must be known (immarg)");
1058case Intrinsic::ctpop:
1059return Ops[0].ctpop();
1075if (NewLower == NewUpper)
1079if (
X.isSizeStrictlySmallerThan(*
this) ||
1080X.isSizeStrictlySmallerThan(
Other))
1081// We've wrapped, therefore, full set. 1089// Calculate the range for "X + Y" which is guaranteed not to wrap(overflow). 1090// (X is from this, and Y is from Other) 1099// If an overflow happens for every value pair in these two constant ranges, 1100// we must return Empty set. In this case, we get that for free, because we 1101// get lucky that intersection of add() with uadd_sat()/sadd_sat() results 1104if (NoWrapKind & OBO::NoSignedWrap)
1107if (NoWrapKind & OBO::NoUnsignedWrap)
1122if (NewLower == NewUpper)
1126if (
X.isSizeStrictlySmallerThan(*
this) ||
1127X.isSizeStrictlySmallerThan(
Other))
1128// We've wrapped, therefore, full set. 1136// Calculate the range for "X - Y" which is guaranteed not to wrap(overflow). 1137// (X is from this, and Y is from Other) 1146// If an overflow happens for every value pair in these two constant ranges, 1147// we must return Empty set. In signed case, we get that for free, because we 1148// get lucky that intersection of sub() with ssub_sat() results in an 1149// empty set. But for unsigned we must perform the overflow check manually. 1151if (NoWrapKind & OBO::NoSignedWrap)
1154if (NoWrapKind & OBO::NoUnsignedWrap) {
1156return getEmpty();
// Always overflows. 1165// TODO: If either operand is a single element and the multiply is known to 1166// be non-wrapping, round the result min and max value to the appropriate 1167// multiple of that element. If wrapping is possible, at least adjust the 1168// range according to the greatest power-of-two factor of the single element. 1187// Multiplication is signedness-independent. However different ranges can be 1188// obtained depending on how the input ranges are treated. These different 1189// ranges are all conservatively correct, but one might be better than the 1190// other. We calculate two ranges; one treating the inputs as unsigned 1191// and the other signed, then return the smallest of these ranges. 1193// Unsigned range first. 1200 this_max * Other_max + 1);
1203// If the unsigned range doesn't wrap, and isn't negative then it's a range 1204// from one positive number to another which is as good as we can generate. 1205// In this case, skip the extra work of generating signed ranges which aren't 1206// going to be better than this range. 1211// Now the signed range. Because we could be dealing with negative numbers 1212// here, the lower bound is the smallest of the cartesian product of the 1213// lower and upper ranges; for example: 1214// [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. 1215// Similarly for the upper bound, swapping min for max. 1222auto L = {this_min * Other_min, this_min * Other_max,
1223 this_max * Other_min, this_max * Other_max};
1224auto Compare = [](
constAPInt &
A,
constAPInt &
B) {
returnA.slt(
B); };
1225ConstantRange Result_sext(std::min(L, Compare), std::max(L, Compare) + 1);
1248// mul nsw nuw X, Y s>= 0 if X s> 1 or Y s> 1 1251 !Result.isAllNonNegative()) {
1253 Result = Result.intersectWith(
1272auto Muls = {Min.
smul_ov(OtherMin, O1), Min.
smul_ov(OtherMax, O2),
1273 Max.smul_ov(OtherMin, O3), Max.smul_ov(OtherMax, O4)};
1274if (O1 || O2 || O3 || O4)
1277auto Compare = [](
constAPInt &
A,
constAPInt &
B) {
returnA.slt(
B); };
1278returngetNonEmpty(std::min(Muls, Compare), std::max(Muls, Compare) + 1);
1283// X smax Y is: range(smax(X_smin, Y_smin), 1284// smax(X_smax, Y_smax)) 1297// X umax Y is: range(umax(X_umin, Y_umin), 1298// umax(X_umax, Y_umax)) 1311// X smin Y is: range(smin(X_smin, Y_smin), 1312// smin(X_smax, Y_smax)) 1325// X umin Y is: range(umin(X_umin, Y_umin), 1326// umin(X_umax, Y_umax)) 1344APInt RHS_umin =
RHS.getUnsignedMin();
1346// We want the lowest value in RHS excluding zero. Usually that would be 1 1347// except for a range in the form of [X, 1) in which case it would be X. 1348if (
RHS.getUpper() == 1)
1349 RHS_umin =
RHS.getLower();
1359// We split up the LHS and RHS into positive and negative components 1360// and then also compute the positive and negative components of the result 1361// separately by combining division results with the appropriate signs. 1364// There are no positive 1-bit values. The 1 would get interpreted as -1. 1378 (PosL.Upper - 1).
sdiv(PosR.Lower) + 1);
1383// We need to deal with one tricky case here: SignedMin / -1 is UB on the 1384// IR level, so we'll want to exclude this case when calculating bounds. 1385// (For APInts the operation is well-defined and yields SignedMin.) We 1386// handle this by dropping either SignedMin from the LHS or -1 from the RHS. 1389// Remove -1 from the LHS. Skip if it's the only element, as this would 1390// leave us with an empty set. 1393if (
RHS.Lower.isAllOnes())
1394// Negative part of [-1, X] without -1 is [SignedMin, X]. 1395 AdjNegRUpper =
RHS.Upper;
1397// [X, -1] without -1 is [X, -2]. 1398 AdjNegRUpper = NegR.Upper - 1;
1404// Remove SignedMin from the RHS. Skip if it's the only element, as this 1405// would leave us with an empty set. 1406if (NegL.Upper != SignedMin + 1) {
1408if (Upper == SignedMin + 1)
1409// Negative part of [X, SignedMin] without SignedMin is [X, -1]. 1410 AdjNegLLower = Lower;
1412// [SignedMin, X] without SignedMin is [SignedMin + 1, X]. 1413 AdjNegLLower = NegL.Lower + 1;
1417 AdjNegLLower.
sdiv(NegR.Upper - 1) + 1));
1428 NegRes =
ConstantRange((PosL.Upper - 1).sdiv(NegR.Upper - 1),
1429 PosL.Lower.
sdiv(NegR.Lower) + 1);
1435 (NegL.Upper - 1).
sdiv(PosR.Upper - 1) + 1));
1437// Prefer a non-wrapping signed range here. 1440// Preserve the zero that we dropped when splitting the LHS by sign. 1450if (
constAPInt *RHSInt =
RHS.getSingleElement()) {
1451// UREM by null is UB. 1452if (RHSInt->isZero())
1454// Use APInt's implementation of UREM for single element ranges. 1456return {LHSInt->urem(*RHSInt)};
1459// L % R for L < R is L. 1463// L % R is <= L and < R. 1472if (
constAPInt *RHSInt =
RHS.getSingleElement()) {
1473// SREM by null is UB. 1474if (RHSInt->isZero())
1476// Use APInt's implementation of SREM for single element ranges. 1478return {LHSInt->srem(*RHSInt)};
1485// Modulus by zero is UB. 1495// L % R for L < R is L. 1496if (MaxLHS.ult(MinAbsRHS))
1499// L % R is <= L and < R. 1504// Same basic logic as above, but the result is negative. 1505if (MaxLHS.isNegative()) {
1506if (MinLHS.
ugt(-MinAbsRHS))
1513// LHS range crosses zero. 1523/// Estimate the 'bit-masked AND' operation's lower bound. 1525/// E.g., given two ranges as follows (single quotes are separators and 1526/// have no meaning here), 1528/// LHS = [10'00101'1, ; LLo 1529/// 10'10000'0] ; LHi 1530/// RHS = [10'11111'0, ; RLo 1531/// 10'11111'1] ; RHi 1533/// we know that the higher 2 bits of the result is always 10; and we also 1534/// notice that RHS[1:6] are always 1, so the result[1:6] cannot be less than 1535/// LHS[1:6] (i.e., 00101). Thus, the lower bound is 10'00101'0. 1537/// The algorithm is as follows, 1538/// 1. we first calculate a mask to find the higher common bits by 1539/// Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo)); 1540/// Mask = clear all non-leading-ones bits in Mask; 1541/// in the example, the Mask is set to 11'00000'0; 1542/// 2. calculate a new mask by setting all common leading bits to 1 in RHS, and 1543/// keeping the longest leading ones (i.e., 11'11111'0 in the example); 1544/// 3. return (LLo & new mask) as the lower bound; 1545/// 4. repeat the step 2 and 3 with LHS and RHS swapped, and update the lower 1546/// bound with the larger one. 1550// If either is full set or unsigned wrapped, then the range must contain '0' 1551// which leads the lower bound to 0. 1552if ((
LHS.isFullSet() ||
RHS.isFullSet()) ||
1553 (
LHS.isWrappedSet() ||
RHS.isWrappedSet()))
1556auto LLo =
LHS.getLower();
1557auto LHi =
LHS.getUpper() - 1;
1558auto RLo =
RHS.getLower();
1559auto RHi =
RHS.getUpper() - 1;
1561// Calculate the mask for the higher common bits. 1562auto Mask = ~((LLo ^ LHi) | (RLo ^ RHi) | (LLo ^ RLo));
1563unsigned LeadingOnes = Mask.countLeadingOnes();
1564 Mask.clearLowBits(
BitWidth - LeadingOnes);
1568unsigned LeadingOnes = ((BLo & BHi) | Mask).countLeadingOnes();
1569unsigned StartBit =
BitWidth - LeadingOnes;
1570 ALo.clearLowBits(StartBit);
1574auto LowerBoundByLHS = estimateBound(LLo, RLo, RHi);
1575auto LowerBoundByRHS = estimateBound(RLo, LLo, LHi);
1600// <=> ~(~a & ~b) <= ~x 1602// <=> a | b < ~x + 1 = -x 1603// thus, UpperBound(a | b) == -LowerBound(~a & ~b) 1606// Upper wrapped range. 1616// Use APInt's implementation of XOR for single element ranges. 1620// Special-case binary complement, since we can give a precise answer. 1621if (
Other.isSingleElement() &&
Other.getSingleElement()->isAllOnes())
1624returnOther.binaryNot();
1630// Typically the following code doesn't improve the result if BW = 1. 1634// If LHS is known to be the subset of RHS, treat LHS ^ RHS as RHS -nuw/nsw 1635// LHS. If RHS is known to be the subset of LHS, treat LHS ^ RHS as LHS 1637if ((~LHSKnown.
Zero).isSubsetOf(RHSKnown.
One))
1639elseif ((~RHSKnown.
Zero).isSubsetOf(LHSKnown.
One))
1656unsigned EqualLeadingBits = (Min ^ Max).
countl_zero();
1657if (
RHS->ule(EqualLeadingBits))
1666// For negative numbers, if the shift does not overflow in a signed sense, 1667// a larger shift will make the number smaller. 1668 Max <<=
Other.getUnsignedMin();
1674if (OtherMax.
ugt(Max.countl_zero()))
1677// FIXME: implement the other tricky cases 1679 Min <<=
Other.getUnsignedMin();
1690unsigned RHSMin =
RHS.getUnsignedMin().getLimitedValue(
BitWidth);
1693return ConstantRange::getEmpty(
BitWidth);
1695unsigned RHSMax =
RHS.getUnsignedMax().getLimitedValue(
BitWidth);
1696APInt MaxShl = MinShl;
1698if (RHSMin <= MaxShAmt)
1699 MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);
1700 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1702if (RHSMin <= RHSMax)
1716return ConstantRange::getEmpty(
BitWidth);
1717APInt MaxShl = MinShl;
1719if (RHSMin <= MaxShAmt)
1720 MaxShl = LHSMax << std::min(RHSMax, MaxShAmt);
1721 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1723if (RHSMin <= RHSMax)
1731unsigned RHSMin,
unsigned RHSMax) {
1736return ConstantRange::getEmpty(
BitWidth);
1737APInt MinShl = MaxShl;
1739if (RHSMin <= MaxShAmt)
1740 MinShl = LHSMin.
shl(std::min(RHSMax, MaxShAmt));
1741 RHSMin = std::max(RHSMin, MaxShAmt + 1);
1743if (RHSMin <= RHSMax)
1751unsigned RHSMin =
RHS.getUnsignedMin().getLimitedValue(
BitWidth);
1752unsigned RHSMax =
RHS.getUnsignedMax().getLimitedValue(
BitWidth);
1772switch (NoWrapKind) {
1803// May straddle zero, so handle both positive and negative cases. 1804// 'PosMax' is the upper bound of the result of the ashr 1805// operation, when Upper of the LHS of ashr is a non-negative. 1806// number. Since ashr of a non-negative number will result in a 1807// smaller number, the Upper value of LHS is shifted right with 1808// the minimum value of 'Other' instead of the maximum value. 1811// 'PosMin' is the lower bound of the result of the ashr 1812// operation, when Lower of the LHS is a non-negative number. 1813// Since ashr of a non-negative number will result in a smaller 1814// number, the Lower value of LHS is shifted right with the 1815// maximum value of 'Other'. 1818// 'NegMax' is the upper bound of the result of the ashr 1819// operation, when Upper of the LHS of ashr is a negative number. 1820// Since 'ashr' of a negative number will result in a bigger 1821// number, the Upper value of LHS is shifted right with the 1822// maximum value of 'Other'. 1825// 'NegMin' is the lower bound of the result of the ashr 1826// operation, when Lower of the LHS of ashr is a negative number. 1827// Since 'ashr' of a negative number will result in a bigger 1828// number, the Lower value of LHS is shifted right with the 1829// minimum value of 'Other'. 1834// Upper and Lower of LHS are non-negative. 1838// Upper and Lower of LHS are negative. 1842// Upper is non-negative and Lower is negative. 1855returngetNonEmpty(std::move(NewL), std::move(NewU));
1864returngetNonEmpty(std::move(NewL), std::move(NewU));
1873returngetNonEmpty(std::move(NewL), std::move(NewU));
1882returngetNonEmpty(std::move(NewL), std::move(NewU));
1891returngetNonEmpty(std::move(NewL), std::move(NewU));
1898// Because we could be dealing with negative numbers here, the lower bound is 1899// the smallest of the cartesian product of the lower and upper ranges; 1901// [-1,4) * [-2,3) = min(-1*-2, -1*2, 3*-2, 3*2) = -6. 1902// Similarly for the upper bound, swapping min for max. 1910 Max.smul_sat(OtherMin), Max.smul_sat(OtherMax)};
1911auto Compare = [](
constAPInt &
A,
constAPInt &
B) {
returnA.slt(
B); };
1912returngetNonEmpty(std::min(L, Compare), std::max(L, Compare) + 1);
1921returngetNonEmpty(std::move(NewL), std::move(NewU));
1929APInt ShAmtMin =
Other.getUnsignedMin(), ShAmtMax =
Other.getUnsignedMax();
1931APInt NewU = Max.sshl_sat(Max.isNegative() ? ShAmtMin : ShAmtMax) + 1;
1932returngetNonEmpty(std::move(NewL), std::move(NewU));
1949// Check whether the range crosses zero. 1955// If SignedMin is not poison, then it is included in the result range. 1964// Skip SignedMin if it is poison. 1965if (IntMinIsPoison &&
SMin.isMinSignedValue()) {
1966// The range may become empty if it *only* contains SignedMin. 1967if (
SMax.isMinSignedValue())
1973if (
SMin.isNonNegative())
1977if (
SMax.isNegative())
1980// Range crosses zero. 1990if (ZeroIsPoison &&
contains(Zero)) {
1991// ZeroIsPoison is set, and zero is contained. We discern three cases, in 1992// which a zero can appear: 1993// 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc. 1994// 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc. 1995// 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc. 1999// We have in input interval of kind [0, 1). In this case we cannot 2000// really help but return empty-set. 2004// Compute the resulting range by excluding zero from Lower. 2009// Compute the resulting range by excluding zero from Upper. 2017// Zero is either safe or not in the range. The output range is composed by 2018// the result of countLeadingZero of the two extremes. 2026"Unexpected wrapped set.");
2035// Calculate longest common prefix. 2036unsigned LCPLength = (
Lower ^ (
Upper - 1)).countl_zero();
2037// If Lower is {LCP, 000...}, the maximum is Lower.countr_zero(). 2038// Otherwise, the maximum is BitWidth - LCPLength - 1 ({LCP, 100...}). 2042 std::max(
BitWidth - LCPLength - 1,
Lower.countr_zero()) + 1));
2051if (ZeroIsPoison &&
contains(Zero)) {
2052// ZeroIsPoison is set, and zero is contained. We discern three cases, in 2053// which a zero can appear: 2054// 1) Lower is zero, handling cases of kind [0, 1), [0, 2), etc. 2055// 2) Upper is zero, wrapped set, handling cases of kind [3, 0], etc. 2056// 3) Zero contained in a wrapped set, e.g., [3, 2), [3, 1), etc. 2060// We have in input interval of kind [0, 1). In this case we cannot 2061// really help but return empty-set. 2065// Compute the resulting range by excluding zero from Lower. 2067 }
elseif (Upper == 1) {
2068// Compute the resulting range by excluding zero from Upper. 2082// The range is wrapped. We decompose it into two ranges, [0, Upper) and 2094"Unexpected wrapped set.");
2101// Calculate longest common prefix. 2103unsigned LCPPopCount =
Lower.getHiBits(LCPLength).popcount();
2104// If Lower is {LCP, 000...}, the minimum is the popcount of LCP. 2105// Otherwise, the minimum is the popcount of LCP + 1. 2107 LCPPopCount + (
Lower.countr_zero() <
BitWidth - LCPLength ? 1 : 0);
2108// If Max is {LCP, 111...}, the maximum is the popcount of LCP + (BitWidth - 2110// Otherwise, the minimum is the popcount of LCP + (BitWidth - 2111// length of LCP - 1). 2112unsigned MaxBits = LCPPopCount + (
BitWidth - LCPLength) -
2113 (Max.countr_one() <
BitWidth - LCPLength ? 1 : 0);
2127// The range is wrapped. We decompose it into two ranges, [0, Upper) and 2129// Handle [Lower, 0) == [Lower, Max] 2143APInt OtherMin =
Other.getUnsignedMin(), OtherMax =
Other.getUnsignedMax();
2145// a u+ b overflows high iff a u> ~b. 2146if (Min.
ugt(~OtherMin))
2148if (Max.ugt(~OtherMax))
2164// a s+ b overflows high iff a s>=0 && b s>= 0 && a s> smax - b. 2165// a s+ b overflows low iff a s< 0 && b s< 0 && a s< smin - b. 2167 Min.
sgt(SignedMax - OtherMin))
2169if (Max.isNegative() && OtherMax.isNegative() &&
2170 Max.slt(SignedMin - OtherMax))
2173if (Max.isNonNegative() && OtherMax.isNonNegative() &&
2174 Max.sgt(SignedMax - OtherMax))
2177 Min.
slt(SignedMin - OtherMin))
2189APInt OtherMin =
Other.getUnsignedMin(), OtherMax =
Other.getUnsignedMax();
2191// a u- b overflows low iff a u< b. 2192if (Max.ult(OtherMin))
2194if (Min.
ult(OtherMax))
2210// a s- b overflows high iff a s>=0 && b s< 0 && a s> smax + b. 2211// a s- b overflows low iff a s< 0 && b s>= 0 && a s< smin + b. 2213 Min.
sgt(SignedMax + OtherMax))
2216 Max.slt(SignedMin + OtherMin))
2219if (Max.isNonNegative() && OtherMin.
isNegative() &&
2220 Max.sgt(SignedMax + OtherMin))
2222if (Min.
isNegative() && OtherMax.isNonNegative() &&
2223 Min.
slt(SignedMin + OtherMax))
2235APInt OtherMin =
Other.getUnsignedMin(), OtherMax =
Other.getUnsignedMax();
2238 (void) Min.
umul_ov(OtherMin, Overflow);
2242 (void) Max.umul_ov(OtherMax, Overflow);
2255OS <<
"[" << Lower <<
"," << Upper <<
")";
2258#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 2265constunsigned NumRanges = Ranges.getNumOperands() / 2;
2266assert(NumRanges >= 1 &&
"Must have at least one range!");
2267assert(Ranges.getNumOperands() % 2 == 0 &&
"Must be a sequence of pairs");
2269auto *FirstLow = mdconst::extract<ConstantInt>(Ranges.getOperand(0));
2270auto *FirstHigh = mdconst::extract<ConstantInt>(Ranges.getOperand(1));
2272ConstantRange CR(FirstLow->getValue(), FirstHigh->getValue());
2274for (
unsigned i = 1; i < NumRanges; ++i) {
2275auto *
Low = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 0));
2276auto *
High = mdconst::extract<ConstantInt>(Ranges.getOperand(2 * i + 1));
2278// Note: unionWith will potentially create a range that contains values not 2279// contained in any of the original N ranges. This file implements a class to represent arbitrary precision integral constant values and operations...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
static APInt estimateBitMaskedAndLowerBound(const ConstantRange &LHS, const ConstantRange &RHS)
Estimate the 'bit-masked AND' operation's lower bound.
static ConstantRange computeShlNUW(const ConstantRange &LHS, const ConstantRange &RHS)
static ConstantRange getUnsignedPopCountRange(const APInt &Lower, const APInt &Upper)
static ConstantRange computeShlNSW(const ConstantRange &LHS, const ConstantRange &RHS)
static ConstantRange makeExactMulNUWRegion(const APInt &V)
Exact mul nuw region for single element RHS.
static ConstantRange computeShlNSWWithNNegLHS(const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)
static ConstantRange makeExactMulNSWRegion(const APInt &V)
Exact mul nsw region for single element RHS.
static ConstantRange getPreferredRange(const ConstantRange &CR1, const ConstantRange &CR2, ConstantRange::PreferredRangeType Type)
static ConstantRange getUnsignedCountTrailingZerosRange(const APInt &Lower, const APInt &Upper)
static ConstantRange computeShlNSWWithNegLHS(const APInt &LHSMin, const APInt &LHSMax, unsigned RHSMin, unsigned RHSMax)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
This file contains the declarations for metadata subclasses.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt usub_sat(const APInt &RHS) const
APInt udiv(const APInt &RHS) const
Unsigned division operation.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
void clearBit(unsigned BitPosition)
Set a given bit to 0.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
bool isMinSignedValue() const
Determine if this is the smallest signed value.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt trunc(unsigned width) const
Truncate to new width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt sshl_ov(const APInt &Amt, bool &Overflow) const
APInt smul_sat(const APInt &RHS) const
unsigned countLeadingOnes() const
APInt sadd_sat(const APInt &RHS) const
bool sgt(const APInt &RHS) const
Signed greater than comparison.
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
bool isMinValue() const
Determine if this is the smallest unsigned value.
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
bool isNegative() const
Determine sign of this APInt.
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
bool sle(const APInt &RHS) const
Signed less or equal comparison.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
APInt sshl_sat(const APInt &RHS) const
APInt ushl_sat(const APInt &RHS) const
APInt ushl_ov(const APInt &Amt, bool &Overflow) const
unsigned countLeadingZeros() const
bool isStrictlyPositive() const
Determine if this APInt Value is positive.
unsigned countl_one() const
Count the number of leading one bits.
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
APInt uadd_sat(const APInt &RHS) const
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
void setAllBits()
Set every bit to 1.
bool getBoolValue() const
Convert APInt to a boolean value.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
APInt sext(unsigned width) const
Sign extend to a new width.
APInt shl(unsigned shiftAmt) const
Left-shift function.
APInt umul_sat(const APInt &RHS) const
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
bool slt(const APInt &RHS) const
Signed less than comparison.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
unsigned countr_one() const
Count the number of trailing one bits.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
void clearSignBit()
Set the sign bit to 0.
APInt ssub_sat(const APInt &RHS) const
bool isMaxValue() const
Determine if this is the largest unsigned value.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_SLE
signed less or equal
@ ICMP_UGE
unsigned greater or equal
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_SGE
signed greater or equal
@ ICMP_ULE
unsigned less or equal
Predicate getInversePredicate() const
For example, EQ -> NE, UGT -> ULE, SLT -> SGE, OEQ -> UNE, UGT -> OLE, OLT -> UGE,...
bool isIntPredicate() const
bool isRelational() const
Return true if the predicate is relational (not EQ or NE).
This class represents a range of values.
ConstantRange multiply(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a multiplication of a value in thi...
ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
bool isUpperSignWrapped() const
Return true if the (exclusive) upper bound wraps around the signed domain.
unsigned getActiveBits() const
Compute the maximal number of active bits needed to represent every value in this range.
ConstantRange zextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
PreferredRangeType
If represented precisely, the result of some range operations may consist of multiple disjoint ranges...
std::optional< ConstantRange > exactUnionWith(const ConstantRange &CR) const
Union the two ranges and return the result if it can be represented exactly, otherwise return std::nu...
bool getEquivalentICmp(CmpInst::Predicate &Pred, APInt &RHS) const
Set up Pred and RHS such that ConstantRange::makeExactICmpRegion(Pred, RHS) == *this.
ConstantRange umul_sat(const ConstantRange &Other) const
Perform an unsigned saturating multiplication of two constant ranges.
static CmpInst::Predicate getEquivalentPredWithFlippedSignedness(CmpInst::Predicate Pred, const ConstantRange &CR1, const ConstantRange &CR2)
If the comparison between constant ranges this and Other is insensitive to the signedness of the comp...
ConstantRange subtract(const APInt &CI) const
Subtract the specified constant from the endpoints of this constant range.
const APInt * getSingleElement() const
If this set contains a single element, return it, otherwise return null.
ConstantRange binaryXor(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
const APInt * getSingleMissingElement() const
If this set contains all but a single element, return it, otherwise return null.
static ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
const APInt & getLower() const
Return the lower value for this range.
OverflowResult unsignedSubMayOverflow(const ConstantRange &Other) const
Return whether unsigned sub of the two ranges always/never overflows.
bool isAllNegative() const
Return true if all values in this range are negative.
ConstantRange truncate(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly smaller than the current typ...
OverflowResult unsignedAddMayOverflow(const ConstantRange &Other) const
Return whether unsigned add of the two ranges always/never overflows.
ConstantRange urem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned remainder operation of...
ConstantRange sshl_sat(const ConstantRange &Other) const
Perform a signed saturating left shift of this constant range by a value in Other.
ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
ConstantRange lshr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a logical right shift of a value i...
KnownBits toKnownBits() const
Return known bits for values in this range.
ConstantRange castOp(Instruction::CastOps CastOp, uint32_t BitWidth) const
Return a new range representing the possible values resulting from an application of the specified ca...
ConstantRange umin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned minimum of a value in ...
APInt getUnsignedMin() const
Return the smallest unsigned value contained in the ConstantRange.
ConstantRange difference(const ConstantRange &CR) const
Subtract the specified range from this range (aka relative complement of the sets).
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
ConstantRange srem(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed remainder operation of a ...
bool icmp(CmpInst::Predicate Pred, const ConstantRange &Other) const
Does the predicate Pred hold between ranges this and Other? NOTE: false does not mean that inverse pr...
ConstantRange sadd_sat(const ConstantRange &Other) const
Perform a signed saturating addition of two constant ranges.
ConstantRange ushl_sat(const ConstantRange &Other) const
Perform an unsigned saturating left shift of this constant range by a value in Other.
static ConstantRange intrinsic(Intrinsic::ID IntrinsicID, ArrayRef< ConstantRange > Ops)
Compute range of intrinsic result for the given operand ranges.
void dump() const
Allow printing from a debugger easily.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
bool isAllPositive() const
Return true if all values in this range are positive.
ConstantRange shl(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a left shift of a value in this ra...
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
bool isSignWrappedSet() const
Return true if this set wraps around the signed domain.
bool isSizeLargerThan(uint64_t MaxSize) const
Compare set size of this range with Value.
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
ConstantRange abs(bool IntMinIsPoison=false) const
Calculate absolute value range.
static bool isIntrinsicSupported(Intrinsic::ID IntrinsicID)
Returns true if ConstantRange calculations are supported for intrinsic with IntrinsicID.
static ConstantRange makeSatisfyingICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the largest range such that all values in the returned range satisfy the given predicate with...
bool isWrappedSet() const
Return true if this set wraps around the unsigned domain.
ConstantRange usub_sat(const ConstantRange &Other) const
Perform an unsigned saturating subtraction of two constant ranges.
ConstantRange uadd_sat(const ConstantRange &Other) const
Perform an unsigned saturating addition of two constant ranges.
ConstantRange overflowingBinaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind) const
Return a new range representing the possible values resulting from an application of the specified ov...
void print(raw_ostream &OS) const
Print out the bounds to a stream.
ConstantRange(uint32_t BitWidth, bool isFullSet)
Initialize a full or empty set for the specified bit width.
OverflowResult unsignedMulMayOverflow(const ConstantRange &Other) const
Return whether unsigned mul of the two ranges always/never overflows.
ConstantRange subWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an subtraction with wrap type NoWr...
bool isSingleElement() const
Return true if this set contains exactly one member.
ConstantRange ssub_sat(const ConstantRange &Other) const
Perform a signed saturating subtraction of two constant ranges.
bool isAllNonNegative() const
Return true if all values in this range are non-negative.
ConstantRange umax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned maximum of a value in ...
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
static ConstantRange makeAllowedICmpRegion(CmpInst::Predicate Pred, const ConstantRange &Other)
Produce the smallest range such that all values that may satisfy the given predicate with any value c...
ConstantRange sdiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed division of a value in th...
const APInt & getUpper() const
Return the upper value for this range.
bool isUpperWrapped() const
Return true if the exclusive upper bound wraps around the unsigned domain.
ConstantRange shlWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from a left shift with wrap type NoWrap...
ConstantRange unionWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the union of this range with another range.
static ConstantRange makeExactICmpRegion(CmpInst::Predicate Pred, const APInt &Other)
Produce the exact range such that all values in the returned range satisfy the given predicate with a...
ConstantRange inverse() const
Return a new range that is the logical not of the current set.
std::optional< ConstantRange > exactIntersectWith(const ConstantRange &CR) const
Intersect the two ranges and return the result if it can be represented exactly, otherwise return std...
ConstantRange ashr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a arithmetic right shift of a valu...
ConstantRange binaryAnd(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-and of a value in this ra...
bool contains(const APInt &Val) const
Return true if the specified value is in the set.
static bool areInsensitiveToSignednessOfInvertedICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 sge CR2.
OverflowResult signedAddMayOverflow(const ConstantRange &Other) const
Return whether signed add of the two ranges always/never overflows.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
ConstantRange addWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from an addition with wrap type NoWrapK...
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
OverflowResult
Represents whether an operation on the given constant range is known to always or never overflow.
@ NeverOverflows
Never overflows.
@ AlwaysOverflowsHigh
Always overflows in the direction of signed/unsigned max value.
@ AlwaysOverflowsLow
Always overflows in the direction of signed/unsigned min value.
@ MayOverflow
May or may not overflow.
static ConstantRange makeMaskNotEqualRange(const APInt &Mask, const APInt &C)
Initialize a range containing all values X that satisfy (X & Mask) != C.
static bool areInsensitiveToSignednessOfICmpPredicate(const ConstantRange &CR1, const ConstantRange &CR2)
Return true iff CR1 ult CR2 is equivalent to CR1 slt CR2.
ConstantRange cttz(bool ZeroIsPoison=false) const
Calculate cttz range.
static ConstantRange getNonEmpty(APInt Lower, APInt Upper)
Create non-empty constant range with the given bounds.
ConstantRange ctpop() const
Calculate ctpop range.
static ConstantRange makeGuaranteedNoWrapRegion(Instruction::BinaryOps BinOp, const ConstantRange &Other, unsigned NoWrapKind)
Produce the largest range containing all X such that "X BinOp Y" is guaranteed not to wrap (overflow)...
ConstantRange smin(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed minimum of a value in thi...
ConstantRange udiv(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an unsigned division of a value in...
unsigned getMinSignedBits() const
Compute the maximal number of bits needed to represent every value in this signed range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange binaryNot() const
Return a new range representing the possible values resulting from a binary-xor of a value in this ra...
ConstantRange smax(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a signed maximum of a value in thi...
ConstantRange binaryOp(Instruction::BinaryOps BinOp, const ConstantRange &Other) const
Return a new range representing the possible values resulting from an application of the specified bi...
ConstantRange binaryOr(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a binary-or of a value in this ran...
OverflowResult signedSubMayOverflow(const ConstantRange &Other) const
Return whether signed sub of the two ranges always/never overflows.
ConstantRange ctlz(bool ZeroIsPoison=false) const
Calculate ctlz range.
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
static ConstantRange makeExactNoWrapRegion(Instruction::BinaryOps BinOp, const APInt &Other, unsigned NoWrapKind)
Produce the range that contains X if and only if "X BinOp Other" does not wrap.
bool isSizeStrictlySmallerThan(const ConstantRange &CR) const
Compare set size of this range with the range CR.
ConstantRange multiplyWithNoWrap(const ConstantRange &Other, unsigned NoWrapKind, PreferredRangeType RangeType=Smallest) const
Return a new range representing the possible values resulting from a multiplication with wrap type No...
Predicate getFlippedSignednessPredicate() const
For example, SLT->ULT, ULT->SLT, SLE->ULE, ULE->SLE, EQ->EQ.
Utility class for integer operators which may exhibit overflow - Add, Sub, Mul, and Shl.
The instances of the Type class are immutable: once they are created, they are never changed.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
std::optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
APInt RoundingSDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A sign-divided by B, rounded by the given rounding mode.
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
@ C
The default llvm calling convention, compatible with C.
This is an optimization pass for GlobalISel generic memory operations.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
@ Low
Lower the current thread's priority such that it does not affect foreground tasks significantly.
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
int countl_zero(T Val)
Count number of 0's from the most significant bit to the least stopping at the first 1.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
@ UMin
Unsigned integer min implemented in terms of select(cmp()).
@ SMax
Signed integer max implemented in terms of select(cmp()).
@ SMin
Signed integer min implemented in terms of select(cmp()).
@ UMax
Unsigned integer max implemented in terms of select(cmp()).
constexpr unsigned BitWidth
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
bool isNonNegative() const
Returns true if this value is known to be non-negative.
bool isUnknown() const
Returns true if we don't know any bits.
bool hasConflict() const
Returns true if there is conflicting information.
unsigned getBitWidth() const
Get the bit width of this value.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
