18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/Support/Debug.h"
28 #define DEBUG_TYPE "int-range-analysis"
42 const APInt &minRight,
44 const APInt &maxRight,
bool isSigned) {
45 std::optional<APInt> maybeMin = op(minLeft, minRight);
46 std::optional<APInt> maybeMax = op(maxLeft, maxRight);
47 if (maybeMin && maybeMax)
56 unsigned width = lhs[0].getBitWidth();
58 isSigned ? APInt::getSignedMaxValue(width) : APInt::getMaxValue(width);
60 isSigned ? APInt::getSignedMinValue(width) :
APInt::getZero(width);
61 for (
const APInt &left : lhs) {
62 for (
const APInt &right : rhs) {
63 std::optional<APInt> maybeThisResult = op(left, right);
66 APInt result = std::move(*maybeThisResult);
67 min = (isSigned ? result.slt(
min) : result.ult(
min)) ? result :
min;
68 max = (isSigned ? result.sgt(
max) : result.ugt(
max)) ? result :
max;
84 llvm::transform(argRanges, std::back_inserter(truncated),
94 LLVM_DEBUG(llvm::dbgs() <<
"Index handling: 64-bit result = " << sixtyFour
95 <<
" 32-bit = " << thirtyTwo <<
"\n");
96 bool truncEqual =
false;
99 truncEqual = (thirtyTwo == sixtyFourAsThirtyTwo);
102 truncEqual = (thirtyTwo.smin() == sixtyFourAsThirtyTwo.
smin() &&
103 thirtyTwo.smax() == sixtyFourAsThirtyTwo.
smax());
106 truncEqual = (thirtyTwo.umin() == sixtyFourAsThirtyTwo.
umin() &&
107 thirtyTwo.umax() == sixtyFourAsThirtyTwo.
umax());
118 unsigned int destWidth) {
119 APInt umin = range.
umin().zext(destWidth);
120 APInt umax = range.
umax().zext(destWidth);
121 APInt smin = range.
smin().sext(destWidth);
122 APInt smax = range.
smax().sext(destWidth);
123 return {umin, umax, smin, smax};
127 unsigned destWidth) {
128 APInt umin = range.
umin().zext(destWidth);
129 APInt umax = range.
umax().zext(destWidth);
134 unsigned destWidth) {
135 APInt smin = range.
smin().sext(destWidth);
136 APInt smax = range.
smax().sext(destWidth);
141 unsigned int destWidth) {
146 bool hasUnsignedRollover =
147 range.
umin().lshr(destWidth) != range.
umax().lshr(destWidth);
149 : range.umin().trunc(destWidth);
150 APInt umax = hasUnsignedRollover ? APInt::getMaxValue(destWidth)
151 : range.umax().trunc(destWidth);
162 APInt sminHighPart = range.
smin().ashr(destWidth - 1);
163 APInt smaxHighPart = range.
smax().ashr(destWidth - 1);
164 bool hasSignedOverflow =
165 (sminHighPart != smaxHighPart) &&
166 !(sminHighPart.isAllOnes() &&
167 (smaxHighPart.isAllOnes() || smaxHighPart.isZero())) &&
168 !(sminHighPart.isZero() && smaxHighPart.isZero());
169 APInt smin = hasSignedOverflow ? APInt::getSignedMinValue(destWidth)
170 : range.smin().trunc(destWidth);
171 APInt smax = hasSignedOverflow ? APInt::getSignedMaxValue(destWidth)
172 : range.smax().trunc(destWidth);
173 return {umin, umax, smin, smax};
184 const APInt &b) -> std::optional<APInt> {
185 bool overflowed =
false;
186 APInt result = a.uadd_ov(b, overflowed);
187 return overflowed ? std::optional<APInt>() : result;
190 const APInt &b) -> std::optional<APInt> {
191 bool overflowed =
false;
192 APInt result = a.sadd_ov(b, overflowed);
193 return overflowed ? std::optional<APInt>() : result;
197 uadd, lhs.
umin(), rhs.umin(), lhs.
umax(), rhs.umax(),
false);
199 sadd, lhs.
smin(), rhs.smin(), lhs.
smax(), rhs.smax(),
true);
212 const APInt &b) -> std::optional<APInt> {
213 bool overflowed =
false;
214 APInt result = a.usub_ov(b, overflowed);
215 return overflowed ? std::optional<APInt>() : result;
218 const APInt &b) -> std::optional<APInt> {
219 bool overflowed =
false;
220 APInt result = a.ssub_ov(b, overflowed);
221 return overflowed ? std::optional<APInt>() : result;
224 usub, lhs.
umin(), rhs.umax(), lhs.
umax(), rhs.umin(),
false);
226 ssub, lhs.
smin(), rhs.smax(), lhs.
smax(), rhs.smin(),
true);
239 const APInt &b) -> std::optional<APInt> {
240 bool overflowed =
false;
241 APInt result = a.umul_ov(b, overflowed);
242 return overflowed ? std::optional<APInt>() : result;
245 const APInt &b) -> std::optional<APInt> {
246 bool overflowed =
false;
247 APInt result = a.smul_ov(b, overflowed);
248 return overflowed ? std::optional<APInt>() : result;
267 const APInt &lhs,
const APInt &rhs,
const APInt &result)>;
272 const APInt &lhsMin = lhs.
umin(), &lhsMax = lhs.
umax(), &rhsMin = rhs.
umin(),
273 &rhsMax = rhs.
umax();
275 if (!rhsMin.isZero()) {
276 auto udiv = [&fixup](
const APInt &a,
277 const APInt &b) -> std::optional<APInt> {
278 return fixup(a, b, a.udiv(b));
280 return minMaxBy(udiv, {lhsMin, lhsMax}, {rhsMin, rhsMax},
290 [](
const APInt &lhs,
const APInt &rhs,
291 const APInt &result) {
return result; });
299 [](
const APInt &lhs,
const APInt &rhs,
300 const APInt &result) -> std::optional<APInt> {
301 if (!lhs.urem(rhs).isZero()) {
302 bool overflowed =
false;
304 result.uadd_ov(APInt(result.getBitWidth(), 1), overflowed);
305 return overflowed ? std::optional<APInt>() : corrected;
319 const APInt &lhsMin = lhs.
smin(), &lhsMax = lhs.
smax(), &rhsMin = rhs.
smin(),
320 &rhsMax = rhs.
smax();
321 bool canDivide = rhsMin.isStrictlyPositive() || rhsMax.isNegative();
324 auto sdiv = [&fixup](
const APInt &a,
325 const APInt &b) -> std::optional<APInt> {
326 bool overflowed =
false;
327 APInt result = a.sdiv_ov(b, overflowed);
328 return overflowed ? std::optional<APInt>() : fixup(a, b, result);
330 return minMaxBy(sdiv, {lhsMin, lhsMax}, {rhsMin, rhsMax},
339 [](
const APInt &lhs,
const APInt &rhs,
340 const APInt &result) {
return result; });
348 [](
const APInt &lhs,
const APInt &rhs,
349 const APInt &result) -> std::optional<APInt> {
350 if (!lhs.srem(rhs).isZero() && lhs.isNonNegative() == rhs.isNonNegative()) {
351 bool overflowed =
false;
353 result.sadd_ov(APInt(result.getBitWidth(), 1), overflowed);
354 return overflowed ? std::optional<APInt>() : corrected;
366 [](
const APInt &lhs,
const APInt &rhs,
367 const APInt &result) -> std::optional<APInt> {
368 if (!lhs.srem(rhs).isZero() && lhs.isNonNegative() != rhs.isNonNegative()) {
369 bool overflowed =
false;
371 result.ssub_ov(APInt(result.getBitWidth(), 1), overflowed);
372 return overflowed ? std::optional<APInt>() : corrected;
386 const APInt &lhsMin = lhs.
smin(), &lhsMax = lhs.
smax(), &rhsMin = rhs.smin(),
387 &rhsMax = rhs.smax();
389 unsigned width = rhsMax.getBitWidth();
390 APInt smin = APInt::getSignedMinValue(width);
391 APInt smax = APInt::getSignedMaxValue(width);
393 bool canBound = (rhsMin.isStrictlyPositive() || rhsMax.isNegative());
395 APInt maxDivisor = rhsMin.isStrictlyPositive() ? rhsMax : rhsMin.abs();
396 bool canNegativeDividend = lhsMin.isNegative();
397 bool canPositiveDividend = lhsMax.isStrictlyPositive();
399 APInt maxPositiveResult = maxDivisor - 1;
400 APInt minNegativeResult = -maxPositiveResult;
401 smin = canNegativeDividend ? minNegativeResult : zero;
402 smax = canPositiveDividend ? maxPositiveResult : zero;
404 if (rhsMin == rhsMax) {
405 if ((lhsMax - lhsMin).
ult(maxDivisor)) {
406 APInt minRem = lhsMin.srem(maxDivisor);
407 APInt maxRem = lhsMax.srem(maxDivisor);
408 if (minRem.sle(maxRem)) {
425 const APInt &rhsMin = rhs.umin(), &rhsMax = rhs.umax();
427 unsigned width = rhsMin.getBitWidth();
429 APInt umax = APInt::getMaxValue(width);
431 if (!rhsMin.isZero()) {
434 if (rhsMin == rhsMax) {
435 const APInt &lhsMin = lhs.
umin(), &lhsMax = lhs.
umax();
436 if ((lhsMax - lhsMin).
ult(rhsMax)) {
437 APInt minRem = lhsMin.urem(rhsMax);
438 APInt maxRem = lhsMax.urem(rhsMax);
439 if (minRem.ule(maxRem)) {
457 const APInt &smin = lhs.
smin().sgt(rhs.smin()) ? lhs.
smin() : rhs.smin();
458 const APInt &smax = lhs.
smax().sgt(rhs.smax()) ? lhs.
smax() : rhs.smax();
466 const APInt &umin = lhs.
umin().ugt(rhs.umin()) ? lhs.
umin() : rhs.umin();
467 const APInt &umax = lhs.
umax().ugt(rhs.umax()) ? lhs.
umax() : rhs.umax();
475 const APInt &smin = lhs.
smin().slt(rhs.smin()) ? lhs.
smin() : rhs.smin();
476 const APInt &smax = lhs.
smax().slt(rhs.smax()) ? lhs.
smax() : rhs.smax();
484 const APInt &umin = lhs.
umin().ult(rhs.umin()) ? lhs.
umin() : rhs.umin();
485 const APInt &umax = lhs.
umax().ult(rhs.umax()) ? lhs.
umax() : rhs.umax();
497 static std::tuple<APInt, APInt>
499 APInt leftVal = bound.
umin(), rightVal = bound.
umax();
500 unsigned bitwidth = leftVal.getBitWidth();
501 unsigned differingBits = bitwidth - (leftVal ^ rightVal).countl_zero();
502 leftVal.clearLowBits(differingBits);
503 rightVal.setLowBits(differingBits);
504 return std::make_tuple(std::move(leftVal), std::move(rightVal));
511 auto andi = [](
const APInt &a,
const APInt &b) -> std::optional<APInt> {
514 return minMaxBy(andi, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
522 auto ori = [](
const APInt &a,
const APInt &b) -> std::optional<APInt> {
525 return minMaxBy(ori, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
533 auto xori = [](
const APInt &a,
const APInt &b) -> std::optional<APInt> {
536 return minMaxBy(xori, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
548 const APInt &r) -> std::optional<APInt> {
549 return r.uge(r.getBitWidth()) ? std::optional<APInt>() : l.shl(r);
565 const APInt &r) -> std::optional<APInt> {
566 return r.uge(r.getBitWidth()) ? std::optional<APInt>() : l.ashr(r);
578 const APInt &r) -> std::optional<APInt> {
579 return r.uge(r.getBitWidth()) ? std::optional<APInt>() : l.lshr(r);
612 llvm_unreachable(
"unknown cmp predicate value");
638 return lhsConst && rhsConst && lhsConst == rhsConst;
static Value getZero(OpBuilder &b, Location loc, Type elementType)
Get zero value for an element type.
static ConstantIntRanges inferDivSRange(const ConstantIntRanges &lhs, const ConstantIntRanges &rhs, DivisionFixupFn fixup)
static bool isStaticallyTrue(intrange::CmpPredicate pred, const ConstantIntRanges &lhs, const ConstantIntRanges &rhs)
static intrange::CmpPredicate invertPredicate(intrange::CmpPredicate pred)
static ConstantIntRanges minMaxBy(ConstArithFn op, ArrayRef< APInt > lhs, ArrayRef< APInt > rhs, bool isSigned)
Compute the minimum and maximum of (op(l, r) for l in lhs for r in rhs), ignoring unbounded values.
static std::tuple< APInt, APInt > widenBitwiseBounds(const ConstantIntRanges &bound)
"Widen" bounds - if 0bvvvvv??? <= a <= 0bvvvvv???, relax the bounds to 0bvvvvv000 <= a <= 0bvvvvv111,...
static ConstantIntRanges inferDivURange(const ConstantIntRanges &lhs, const ConstantIntRanges &rhs, DivisionFixupFn fixup)
static ConstantIntRanges computeBoundsBy(ConstArithFn op, const APInt &minLeft, const APInt &minRight, const APInt &maxLeft, const APInt &maxRight, bool isSigned)
Compute op(minLeft, minRight) and op(maxLeft, maxRight) if possible, If either computation overflows,...
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
static Value min(ImplicitLocOpBuilder &builder, Value value, Value bound)
A set of arbitrary-precision integers representing bounds on a given integer value.
static ConstantIntRanges maxRange(unsigned bitwidth)
Create a ConstantIntRanges with the maximum bounds for the width bitwidth, that is - [0,...
const APInt & smax() const
The maximum value of an integer when it is interpreted as signed.
static ConstantIntRanges fromUnsigned(const APInt &umin, const APInt &umax)
Create an ConstantIntRanges with the unsigned minimum and maximum equal to umin and umax and the sign...
const APInt & smin() const
The minimum value of an integer when it is interpreted as signed.
static ConstantIntRanges range(const APInt &min, const APInt &max, bool isSigned)
Create a ConstantIntRanges whose minimum is min and maximum is max with isSigned specifying if the mi...
ConstantIntRanges intersection(const ConstantIntRanges &other) const
Returns the intersection (computed separately for signed and unsigned bounds) of this range and other...
static ConstantIntRanges fromSigned(const APInt &smin, const APInt &smax)
Create an ConstantIntRanges with the signed minimum and maximum equal to smin and smax,...
std::optional< APInt > getConstantValue() const
If either the signed or unsigned interpretations of the range indicate that the value it bounds is a ...
const APInt & umax() const
The maximum value of an integer when it is interpreted as unsigned.
const APInt & umin() const
The minimum value of an integer when it is interpreted as unsigned.
ConstantIntRanges rangeUnion(const ConstantIntRanges &other) const
Returns the union (computed separately for signed and unsigned bounds) of this range and other.
ConstantIntRanges inferAnd(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferAdd(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferSub(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferShrS(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferIndexOp(InferRangeFn inferFn, ArrayRef< ConstantIntRanges > argRanges, CmpMode mode)
Compute inferFn on ranges, whose size should be the index storage bitwidth.
ConstantIntRanges extSIRange(const ConstantIntRanges &range, unsigned destWidth)
Use the signed values in range to sign-extend it to destWidth.
std::optional< bool > evaluatePred(CmpPredicate pred, const ConstantIntRanges &lhs, const ConstantIntRanges &rhs)
Returns a boolean value if pred is statically true or false for anypossible inputs falling within lhs...
ConstantIntRanges inferMinS(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferMaxU(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferRemS(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferMul(ArrayRef< ConstantIntRanges > argRanges)
CmpPredicate
Copy of the enum from arith and index to allow the common integer range infrastructure to not depend ...
ConstantIntRanges inferOr(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges extRange(const ConstantIntRanges &range, unsigned destWidth)
Independently zero-extend the unsigned values and sign-extend the signed values in range to destWidth...
ConstantIntRanges truncRange(const ConstantIntRanges &range, unsigned destWidth)
Truncate range to destWidth bits, taking care to handle cases such as the truncation of [255,...
ConstantIntRanges inferDivU(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferCeilDivS(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferMinU(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferXor(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferDivS(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferShrU(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferRemU(ArrayRef< ConstantIntRanges > argRanges)
static constexpr unsigned indexMinWidth
ConstantIntRanges inferFloorDivS(ArrayRef< ConstantIntRanges > argRanges)
static constexpr unsigned indexMaxWidth
ConstantIntRanges inferCeilDivU(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges extUIRange(const ConstantIntRanges &range, unsigned destWidth)
Use the unsigned values in range to zero-extend it to destWidth.
ConstantIntRanges inferShl(ArrayRef< ConstantIntRanges > argRanges)
ConstantIntRanges inferMaxS(ArrayRef< ConstantIntRanges > argRanges)
This header declares functions that assist transformations in the MemRef dialect.