1//===- InferIntRangeCommon.cpp - Inference for common ops ------------===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8//
9// This file contains implementations of range inference for operations that are
10// common to both the `arith` and `index` dialects to facilitate reuse.
11//
12//===----------------------------------------------------------------------===//
13
14#include "mlir/Interfaces/Utils/InferIntRangeCommon.h"
15
16#include "mlir/IR/AffineExpr.h"
17#include "mlir/Interfaces/InferIntRangeInterface.h"
18#include "mlir/Interfaces/ShapedOpInterfaces.h"
19
20#include "llvm/ADT/ArrayRef.h"
21#include "llvm/ADT/STLExtras.h"
22
23#include "llvm/Support/Debug.h"
24
25#include <array>
26#include <iterator>
27#include <optional>
28#include <utility>
29
30using namespace mlir;
31
32#define DEBUG_TYPE "int-range-analysis"
33
34//===----------------------------------------------------------------------===//
35// General utilities
36//===----------------------------------------------------------------------===//
37
38/// Function that evaluates the result of doing something on arithmetic
39/// constants and returns std::nullopt on overflow.
40using ConstArithFn =
41 function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
42using ConstArithStdFn =
43 std::function<std::optional<APInt>(const APInt &, const APInt &)>;
44
45/// Compute op(minLeft, minRight) and op(maxLeft, maxRight) if possible,
46/// If either computation overflows, make the result unbounded.
47static ConstantIntRanges computeBoundsBy(ConstArithFn op, const APInt &minLeft,
48 const APInt &minRight,
49 const APInt &maxLeft,
50 const APInt &maxRight, bool isSigned) {
51 std::optional<APInt> maybeMin = op(minLeft, minRight);
52 std::optional<APInt> maybeMax = op(maxLeft, maxRight);
53 if (maybeMin && maybeMax)
54 return ConstantIntRanges::range(min: *maybeMin, max: *maybeMax, isSigned);
55 return ConstantIntRanges::maxRange(bitwidth: minLeft.getBitWidth());
56}
57
58/// Compute the minimum and maximum of `(op(l, r) for l in lhs for r in rhs)`,
59/// ignoring unbounded values. Returns the maximal range if `op` overflows.
60static ConstantIntRanges minMaxBy(ConstArithFn op, ArrayRef<APInt> lhs,
61 ArrayRef<APInt> rhs, bool isSigned) {
62 unsigned width = lhs[0].getBitWidth();
63 APInt min =
64 isSigned ? APInt::getSignedMaxValue(numBits: width) : APInt::getMaxValue(numBits: width);
65 APInt max =
66 isSigned ? APInt::getSignedMinValue(numBits: width) : APInt::getZero(numBits: width);
67 for (const APInt &left : lhs) {
68 for (const APInt &right : rhs) {
69 std::optional<APInt> maybeThisResult = op(left, right);
70 if (!maybeThisResult)
71 return ConstantIntRanges::maxRange(bitwidth: width);
72 APInt result = std::move(*maybeThisResult);
73 min = (isSigned ? result.slt(RHS: min) : result.ult(RHS: min)) ? result : min;
74 max = (isSigned ? result.sgt(RHS: max) : result.ugt(RHS: max)) ? result : max;
75 }
76 }
77 return ConstantIntRanges::range(min, max, isSigned);
78}
79
80//===----------------------------------------------------------------------===//
81// Ext, trunc, index op handling
82//===----------------------------------------------------------------------===//
83
84ConstantIntRanges
85mlir::intrange::inferIndexOp(const InferRangeFn &inferFn,
86 ArrayRef<ConstantIntRanges> argRanges,
87 intrange::CmpMode mode) {
88 ConstantIntRanges sixtyFour = inferFn(argRanges);
89 SmallVector<ConstantIntRanges, 2> truncated;
90 llvm::transform(Range&: argRanges, d_first: std::back_inserter(x&: truncated),
91 F: [](const ConstantIntRanges &range) {
92 return truncRange(range, /*destWidth=*/indexMinWidth);
93 });
94 ConstantIntRanges thirtyTwo = inferFn(truncated);
95 ConstantIntRanges thirtyTwoAsSixtyFour =
96 extRange(range: thirtyTwo, /*destWidth=*/indexMaxWidth);
97 ConstantIntRanges sixtyFourAsThirtyTwo =
98 truncRange(range: sixtyFour, /*destWidth=*/indexMinWidth);
99
100 LLVM_DEBUG(llvm::dbgs() << "Index handling: 64-bit result = " << sixtyFour
101 << " 32-bit = " << thirtyTwo << "\n");
102 bool truncEqual = false;
103 switch (mode) {
104 case intrange::CmpMode::Both:
105 truncEqual = (thirtyTwo == sixtyFourAsThirtyTwo);
106 break;
107 case intrange::CmpMode::Signed:
108 truncEqual = (thirtyTwo.smin() == sixtyFourAsThirtyTwo.smin() &&
109 thirtyTwo.smax() == sixtyFourAsThirtyTwo.smax());
110 break;
111 case intrange::CmpMode::Unsigned:
112 truncEqual = (thirtyTwo.umin() == sixtyFourAsThirtyTwo.umin() &&
113 thirtyTwo.umax() == sixtyFourAsThirtyTwo.umax());
114 break;
115 }
116 if (truncEqual)
117 // Returing the 64-bit result preserves more information.
118 return sixtyFour;
119 ConstantIntRanges merged = sixtyFour.rangeUnion(other: thirtyTwoAsSixtyFour);
120 return merged;
121}
122
123ConstantIntRanges mlir::intrange::extRange(const ConstantIntRanges &range,
124 unsigned int destWidth) {
125 APInt umin = range.umin().zext(width: destWidth);
126 APInt umax = range.umax().zext(width: destWidth);
127 APInt smin = range.smin().sext(width: destWidth);
128 APInt smax = range.smax().sext(width: destWidth);
129 return {umin, umax, smin, smax};
130}
131
132ConstantIntRanges mlir::intrange::extUIRange(const ConstantIntRanges &range,
133 unsigned destWidth) {
134 APInt umin = range.umin().zext(width: destWidth);
135 APInt umax = range.umax().zext(width: destWidth);
136 return ConstantIntRanges::fromUnsigned(umin, umax);
137}
138
139ConstantIntRanges mlir::intrange::extSIRange(const ConstantIntRanges &range,
140 unsigned destWidth) {
141 APInt smin = range.smin().sext(width: destWidth);
142 APInt smax = range.smax().sext(width: destWidth);
143 return ConstantIntRanges::fromSigned(smin, smax);
144}
145
146ConstantIntRanges mlir::intrange::truncRange(const ConstantIntRanges &range,
147 unsigned int destWidth) {
148 // If you truncate the first four bytes in [0xaaaabbbb, 0xccccbbbb],
149 // the range of the resulting value is not contiguous ind includes 0.
150 // Ex. If you truncate [256, 258] from i16 to i8, you validly get [0, 2],
151 // but you can't truncate [255, 257] similarly.
152 bool hasUnsignedRollover =
153 range.umin().lshr(shiftAmt: destWidth) != range.umax().lshr(shiftAmt: destWidth);
154 APInt umin = hasUnsignedRollover ? APInt::getZero(numBits: destWidth)
155 : range.umin().trunc(width: destWidth);
156 APInt umax = hasUnsignedRollover ? APInt::getMaxValue(numBits: destWidth)
157 : range.umax().trunc(width: destWidth);
158
159 // Signed post-truncation rollover will not occur when either:
160 // - The high parts of the min and max, plus the sign bit, are the same
161 // - The high halves + sign bit of the min and max are either all 1s or all 0s
162 // and you won't create a [positive, negative] range by truncating.
163 // For example, you can truncate the ranges [256, 258]_i16 to [0, 2]_i8
164 // but not [255, 257]_i16 to a range of i8s. You can also truncate
165 // [-256, -256]_i16 to [-2, 0]_i8, but not [-257, -255]_i16.
166 // You can also truncate [-130, 0]_i16 to i8 because -130_i16 (0xff7e)
167 // will truncate to 0x7e, which is greater than 0
168 APInt sminHighPart = range.smin().ashr(ShiftAmt: destWidth - 1);
169 APInt smaxHighPart = range.smax().ashr(ShiftAmt: destWidth - 1);
170 bool hasSignedOverflow =
171 (sminHighPart != smaxHighPart) &&
172 !(sminHighPart.isAllOnes() &&
173 (smaxHighPart.isAllOnes() || smaxHighPart.isZero())) &&
174 !(sminHighPart.isZero() && smaxHighPart.isZero());
175 APInt smin = hasSignedOverflow ? APInt::getSignedMinValue(numBits: destWidth)
176 : range.smin().trunc(width: destWidth);
177 APInt smax = hasSignedOverflow ? APInt::getSignedMaxValue(numBits: destWidth)
178 : range.smax().trunc(width: destWidth);
179 return {umin, umax, smin, smax};
180}
181
182//===----------------------------------------------------------------------===//
183// Addition
184//===----------------------------------------------------------------------===//
185
186ConstantIntRanges
187mlir::intrange::inferAdd(ArrayRef<ConstantIntRanges> argRanges,
188 OverflowFlags ovfFlags) {
189 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
190
191 ConstArithStdFn uadd = [=](const APInt &a,
192 const APInt &b) -> std::optional<APInt> {
193 bool overflowed = false;
194 APInt result = any(Val: ovfFlags & OverflowFlags::Nuw)
195 ? a.uadd_sat(RHS: b)
196 : a.uadd_ov(RHS: b, Overflow&: overflowed);
197 return overflowed ? std::optional<APInt>() : result;
198 };
199 ConstArithStdFn sadd = [=](const APInt &a,
200 const APInt &b) -> std::optional<APInt> {
201 bool overflowed = false;
202 APInt result = any(Val: ovfFlags & OverflowFlags::Nsw)
203 ? a.sadd_sat(RHS: b)
204 : a.sadd_ov(RHS: b, Overflow&: overflowed);
205 return overflowed ? std::optional<APInt>() : result;
206 };
207
208 ConstantIntRanges urange = computeBoundsBy(
209 op: uadd, minLeft: lhs.umin(), minRight: rhs.umin(), maxLeft: lhs.umax(), maxRight: rhs.umax(), /*isSigned=*/false);
210 ConstantIntRanges srange = computeBoundsBy(
211 op: sadd, minLeft: lhs.smin(), minRight: rhs.smin(), maxLeft: lhs.smax(), maxRight: rhs.smax(), /*isSigned=*/true);
212 return urange.intersection(other: srange);
213}
214
215//===----------------------------------------------------------------------===//
216// Subtraction
217//===----------------------------------------------------------------------===//
218
219ConstantIntRanges
220mlir::intrange::inferSub(ArrayRef<ConstantIntRanges> argRanges,
221 OverflowFlags ovfFlags) {
222 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
223
224 ConstArithStdFn usub = [=](const APInt &a,
225 const APInt &b) -> std::optional<APInt> {
226 bool overflowed = false;
227 APInt result = any(Val: ovfFlags & OverflowFlags::Nuw)
228 ? a.usub_sat(RHS: b)
229 : a.usub_ov(RHS: b, Overflow&: overflowed);
230 return overflowed ? std::optional<APInt>() : result;
231 };
232 ConstArithStdFn ssub = [=](const APInt &a,
233 const APInt &b) -> std::optional<APInt> {
234 bool overflowed = false;
235 APInt result = any(Val: ovfFlags & OverflowFlags::Nsw)
236 ? a.ssub_sat(RHS: b)
237 : a.ssub_ov(RHS: b, Overflow&: overflowed);
238 return overflowed ? std::optional<APInt>() : result;
239 };
240 ConstantIntRanges urange = computeBoundsBy(
241 op: usub, minLeft: lhs.umin(), minRight: rhs.umax(), maxLeft: lhs.umax(), maxRight: rhs.umin(), /*isSigned=*/false);
242 ConstantIntRanges srange = computeBoundsBy(
243 op: ssub, minLeft: lhs.smin(), minRight: rhs.smax(), maxLeft: lhs.smax(), maxRight: rhs.smin(), /*isSigned=*/true);
244 return urange.intersection(other: srange);
245}
246
247//===----------------------------------------------------------------------===//
248// Multiplication
249//===----------------------------------------------------------------------===//
250
251ConstantIntRanges
252mlir::intrange::inferMul(ArrayRef<ConstantIntRanges> argRanges,
253 OverflowFlags ovfFlags) {
254 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
255
256 ConstArithStdFn umul = [=](const APInt &a,
257 const APInt &b) -> std::optional<APInt> {
258 bool overflowed = false;
259 APInt result = any(Val: ovfFlags & OverflowFlags::Nuw)
260 ? a.umul_sat(RHS: b)
261 : a.umul_ov(RHS: b, Overflow&: overflowed);
262 return overflowed ? std::optional<APInt>() : result;
263 };
264 ConstArithStdFn smul = [=](const APInt &a,
265 const APInt &b) -> std::optional<APInt> {
266 bool overflowed = false;
267 APInt result = any(Val: ovfFlags & OverflowFlags::Nsw)
268 ? a.smul_sat(RHS: b)
269 : a.smul_ov(RHS: b, Overflow&: overflowed);
270 return overflowed ? std::optional<APInt>() : result;
271 };
272
273 ConstantIntRanges urange =
274 minMaxBy(op: umul, lhs: {lhs.umin(), lhs.umax()}, rhs: {rhs.umin(), rhs.umax()},
275 /*isSigned=*/false);
276 ConstantIntRanges srange =
277 minMaxBy(op: smul, lhs: {lhs.smin(), lhs.smax()}, rhs: {rhs.smin(), rhs.smax()},
278 /*isSigned=*/true);
279 return urange.intersection(other: srange);
280}
281
282//===----------------------------------------------------------------------===//
283// DivU, CeilDivU (Unsigned division)
284//===----------------------------------------------------------------------===//
285
286/// Fix up division results (ex. for ceiling and floor), returning an APInt
287/// if there has been no overflow
288using DivisionFixupFn = function_ref<std::optional<APInt>(
289 const APInt &lhs, const APInt &rhs, const APInt &result)>;
290
291static ConstantIntRanges inferDivURange(const ConstantIntRanges &lhs,
292 const ConstantIntRanges &rhs,
293 DivisionFixupFn fixup) {
294 const APInt &lhsMin = lhs.umin(), &lhsMax = lhs.umax(), &rhsMin = rhs.umin(),
295 &rhsMax = rhs.umax();
296 if (!rhsMin.isZero() && !rhsMax.isZero()) {
297 auto udiv = [&fixup](const APInt &a,
298 const APInt &b) -> std::optional<APInt> {
299 return fixup(a, b, a.udiv(RHS: b));
300 };
301 return minMaxBy(op: udiv, lhs: {lhsMin, lhsMax}, rhs: {rhsMin, rhsMax},
302 /*isSigned=*/false);
303 }
304
305 APInt umin = APInt::getZero(numBits: rhsMin.getBitWidth());
306 if (lhsMin.uge(RHS: rhsMax) && !rhsMax.isZero())
307 umin = lhsMin.udiv(RHS: rhsMax);
308
309 // X u/ Y u<= X.
310 const APInt &umax = lhsMax;
311 return ConstantIntRanges::fromUnsigned(umin, umax);
312}
313
314ConstantIntRanges
315mlir::intrange::inferDivU(ArrayRef<ConstantIntRanges> argRanges) {
316 return inferDivURange(lhs: argRanges[0], rhs: argRanges[1],
317 fixup: [](const APInt &lhs, const APInt &rhs,
318 const APInt &result) { return result; });
319}
320
321ConstantIntRanges
322mlir::intrange::inferCeilDivU(ArrayRef<ConstantIntRanges> argRanges) {
323 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
324
325 auto ceilDivUIFix = [](const APInt &lhs, const APInt &rhs,
326 const APInt &result) -> std::optional<APInt> {
327 if (!lhs.urem(RHS: rhs).isZero()) {
328 bool overflowed = false;
329 APInt corrected =
330 result.uadd_ov(RHS: APInt(result.getBitWidth(), 1), Overflow&: overflowed);
331 return overflowed ? std::optional<APInt>() : corrected;
332 }
333 return result;
334 };
335 return inferDivURange(lhs, rhs, fixup: ceilDivUIFix);
336}
337
338//===----------------------------------------------------------------------===//
339// DivS, CeilDivS, FloorDivS (Signed division)
340//===----------------------------------------------------------------------===//
341
342static ConstantIntRanges inferDivSRange(const ConstantIntRanges &lhs,
343 const ConstantIntRanges &rhs,
344 DivisionFixupFn fixup) {
345 const APInt &lhsMin = lhs.smin(), &lhsMax = lhs.smax(), &rhsMin = rhs.smin(),
346 &rhsMax = rhs.smax();
347 // An empty (min > max) divisor range can arise from poison, e.g. a
348 // saturated `nsw`/`nuw` subtraction. Don't trust its bounds.
349 unsigned width = rhsMin.getBitWidth();
350 if (rhsMin.sgt(RHS: rhsMax))
351 return ConstantIntRanges::maxRange(bitwidth: width);
352 bool canDivide = rhsMin.isStrictlyPositive() || rhsMax.isNegative();
353
354 if (canDivide) {
355 auto sdiv = [&fixup](const APInt &a,
356 const APInt &b) -> std::optional<APInt> {
357 bool overflowed = false;
358 APInt result = a.sdiv_ov(RHS: b, Overflow&: overflowed);
359 return overflowed ? std::optional<APInt>() : fixup(a, b, result);
360 };
361 return minMaxBy(op: sdiv, lhs: {lhsMin, lhsMax}, rhs: {rhsMin, rhsMax},
362 /*isSigned=*/true);
363 }
364 // Zero divisors produce poison. Bound each nonzero interval separately.
365 std::optional<ConstantIntRanges> result;
366 if (rhsMin.isNegative())
367 result = inferDivSRange(
368 lhs, rhs: ConstantIntRanges::fromSigned(smin: rhsMin, smax: APInt::getAllOnes(numBits: width)),
369 fixup);
370 if (rhsMax.isStrictlyPositive()) {
371 ConstantIntRanges positive = inferDivSRange(
372 lhs, rhs: ConstantIntRanges::fromSigned(smin: APInt(width, 1), smax: rhsMax), fixup);
373 result = result ? result->rangeUnion(other: positive) : positive;
374 }
375 return result.value_or(u: ConstantIntRanges::maxRange(bitwidth: width));
376}
377
378ConstantIntRanges
379mlir::intrange::inferDivS(ArrayRef<ConstantIntRanges> argRanges) {
380 return inferDivSRange(lhs: argRanges[0], rhs: argRanges[1],
381 fixup: [](const APInt &lhs, const APInt &rhs,
382 const APInt &result) { return result; });
383}
384
385ConstantIntRanges
386mlir::intrange::inferCeilDivS(ArrayRef<ConstantIntRanges> argRanges) {
387 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
388
389 auto ceilDivSIFix = [](const APInt &lhs, const APInt &rhs,
390 const APInt &result) -> std::optional<APInt> {
391 if (!lhs.srem(RHS: rhs).isZero() && lhs.isNonNegative() == rhs.isNonNegative()) {
392 bool overflowed = false;
393 APInt corrected =
394 result.sadd_ov(RHS: APInt(result.getBitWidth(), 1), Overflow&: overflowed);
395 return overflowed ? std::optional<APInt>() : corrected;
396 }
397 // Special case where the usual implementation of ceilDiv causes
398 // INT_MIN / [positive number] to be positive. This doesn't match the
399 // definition of signed ceiling division mathematically, but it prevents
400 // inconsistent constant-folding results. This arises because (-int_min) is
401 // still negative, so -(-int_min / b) is -(int_min / b), which is
402 // positive See #115293.
403 if (lhs.isMinSignedValue() && rhs.sgt(RHS: 1)) {
404 return -result;
405 }
406 return result;
407 };
408 ConstantIntRanges result = inferDivSRange(lhs, rhs, fixup: ceilDivSIFix);
409 if (lhs.smin().isMinSignedValue() && lhs.smax().sgt(RHS: lhs.smin())) {
410 // If lhs range includes INT_MIN and lhs is not a single value, we can
411 // suddenly wrap to positive val, skipping entire negative range, add
412 // [INT_MIN + 1, smax()] range to the result to handle this.
413 auto newLhs = ConstantIntRanges::fromSigned(smin: lhs.smin() + 1, smax: lhs.smax());
414 result = result.rangeUnion(other: inferDivSRange(lhs: newLhs, rhs, fixup: ceilDivSIFix));
415 }
416 if (lhs.smin().isMinSignedValue() && rhs.smax().sgt(RHS: 1) && rhs.smin().sle(RHS: 2)) {
417 // The sign changes between divisors 1 and 2. Include the positive peak.
418 APInt two(lhs.smin().getBitWidth(), 2);
419 result =
420 result.rangeUnion(other: ConstantIntRanges::constant(value: -lhs.smin().sdiv(RHS: two)));
421 }
422 return result;
423}
424
425ConstantIntRanges
426mlir::intrange::inferFloorDivS(ArrayRef<ConstantIntRanges> argRanges) {
427 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
428
429 auto floorDivSIFix = [](const APInt &lhs, const APInt &rhs,
430 const APInt &result) -> std::optional<APInt> {
431 if (!lhs.srem(RHS: rhs).isZero() && lhs.isNonNegative() != rhs.isNonNegative()) {
432 bool overflowed = false;
433 APInt corrected =
434 result.ssub_ov(RHS: APInt(result.getBitWidth(), 1), Overflow&: overflowed);
435 return overflowed ? std::optional<APInt>() : corrected;
436 }
437 return result;
438 };
439 return inferDivSRange(lhs, rhs, fixup: floorDivSIFix);
440}
441
442//===----------------------------------------------------------------------===//
443// Signed remainder (RemS)
444//===----------------------------------------------------------------------===//
445
446ConstantIntRanges
447mlir::intrange::inferRemS(ArrayRef<ConstantIntRanges> argRanges) {
448 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
449 const APInt &lhsMin = lhs.smin(), &lhsMax = lhs.smax(), &rhsMin = rhs.smin(),
450 &rhsMax = rhs.smax();
451
452 unsigned width = rhsMax.getBitWidth();
453 if (rhsMin.sgt(RHS: rhsMax) || (rhsMin.isZero() && rhsMax.isZero()))
454 return ConstantIntRanges::maxRange(bitwidth: width);
455
456 // Magnitudes are unsigned: abs(INT_MIN) is not a positive signed value.
457 APInt maxDivisor = llvm::APIntOps::umax(A: rhsMin.abs(), B: rhsMax.abs());
458 APInt zero = APInt::getZero(numBits: width);
459 APInt maxPositiveResult = maxDivisor - 1;
460 // Remainder has the dividend's sign and cannot exceed its magnitude.
461 APInt smin = llvm::APIntOps::smax(A: llvm::APIntOps::smin(A: lhsMin, B: zero),
462 B: -maxPositiveResult);
463 APInt smax = llvm::APIntOps::smin(A: llvm::APIntOps::smax(A: lhsMax, B: zero),
464 B: maxPositiveResult);
465 // Special case: sweeping out a contiguous range in N/[modulus].
466 if (rhsMin == rhsMax) {
467 if ((lhsMax - lhsMin).ult(RHS: maxDivisor)) {
468 APInt minRem = lhsMin.srem(RHS: maxDivisor);
469 APInt maxRem = lhsMax.srem(RHS: maxDivisor);
470 if (minRem.sle(RHS: maxRem)) {
471 smin = std::move(minRem);
472 smax = std::move(maxRem);
473 }
474 }
475 }
476 return ConstantIntRanges::fromSigned(smin, smax);
477}
478
479//===----------------------------------------------------------------------===//
480// Unsigned remainder (RemU)
481//===----------------------------------------------------------------------===//
482
483ConstantIntRanges
484mlir::intrange::inferRemU(ArrayRef<ConstantIntRanges> argRanges) {
485 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
486 const APInt &rhsMin = rhs.umin(), &rhsMax = rhs.umax();
487
488 unsigned width = rhsMin.getBitWidth();
489 APInt umin = APInt::getZero(numBits: width);
490 // Remainder can't be larger than either of its arguments.
491 APInt umax = llvm::APIntOps::umin(A: (rhsMax - 1), B: lhs.umax());
492
493 if (!rhsMin.isZero()) {
494 // Special case: sweeping out a contiguous range in N/[modulus]
495 if (rhsMin == rhsMax) {
496 const APInt &lhsMin = lhs.umin(), &lhsMax = lhs.umax();
497 if ((lhsMax - lhsMin).ult(RHS: rhsMax)) {
498 APInt minRem = lhsMin.urem(RHS: rhsMax);
499 APInt maxRem = lhsMax.urem(RHS: rhsMax);
500 if (minRem.ule(RHS: maxRem)) {
501 umin = std::move(minRem);
502 umax = std::move(maxRem);
503 }
504 }
505 }
506 }
507 return ConstantIntRanges::fromUnsigned(umin, umax);
508}
509
510//===----------------------------------------------------------------------===//
511// Max and min (MaxS, MaxU, MinS, MinU)
512//===----------------------------------------------------------------------===//
513
514ConstantIntRanges
515mlir::intrange::inferMaxS(ArrayRef<ConstantIntRanges> argRanges) {
516 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
517
518 const APInt &smin = lhs.smin().sgt(RHS: rhs.smin()) ? lhs.smin() : rhs.smin();
519 const APInt &smax = lhs.smax().sgt(RHS: rhs.smax()) ? lhs.smax() : rhs.smax();
520 return ConstantIntRanges::fromSigned(smin, smax);
521}
522
523ConstantIntRanges
524mlir::intrange::inferMaxU(ArrayRef<ConstantIntRanges> argRanges) {
525 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
526
527 const APInt &umin = lhs.umin().ugt(RHS: rhs.umin()) ? lhs.umin() : rhs.umin();
528 const APInt &umax = lhs.umax().ugt(RHS: rhs.umax()) ? lhs.umax() : rhs.umax();
529 return ConstantIntRanges::fromUnsigned(umin, umax);
530}
531
532ConstantIntRanges
533mlir::intrange::inferMinS(ArrayRef<ConstantIntRanges> argRanges) {
534 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
535
536 const APInt &smin = lhs.smin().slt(RHS: rhs.smin()) ? lhs.smin() : rhs.smin();
537 const APInt &smax = lhs.smax().slt(RHS: rhs.smax()) ? lhs.smax() : rhs.smax();
538 return ConstantIntRanges::fromSigned(smin, smax);
539}
540
541ConstantIntRanges
542mlir::intrange::inferMinU(ArrayRef<ConstantIntRanges> argRanges) {
543 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
544
545 const APInt &umin = lhs.umin().ult(RHS: rhs.umin()) ? lhs.umin() : rhs.umin();
546 const APInt &umax = lhs.umax().ult(RHS: rhs.umax()) ? lhs.umax() : rhs.umax();
547 return ConstantIntRanges::fromUnsigned(umin, umax);
548}
549
550//===----------------------------------------------------------------------===//
551// Bitwise operators (And, Or, Xor)
552//===----------------------------------------------------------------------===//
553
554/// "Widen" bounds - if 0bvvvvv??? <= a <= 0bvvvvv???,
555/// relax the bounds to 0bvvvvv000 <= a <= 0bvvvvv111, where vvvvv are the bits
556/// that both bonuds have in common. This gives us a consertive approximation
557/// for what values can be passed to bitwise operations.
558static std::tuple<APInt, APInt>
559widenBitwiseBounds(const ConstantIntRanges &bound) {
560 APInt leftVal = bound.umin(), rightVal = bound.umax();
561 unsigned bitwidth = leftVal.getBitWidth();
562 unsigned differingBits = bitwidth - (leftVal ^ rightVal).countl_zero();
563 leftVal.clearLowBits(loBits: differingBits);
564 rightVal.setLowBits(differingBits);
565 return std::make_tuple(args: std::move(leftVal), args: std::move(rightVal));
566}
567
568ConstantIntRanges
569mlir::intrange::inferAnd(ArrayRef<ConstantIntRanges> argRanges) {
570 auto [lhsZeros, lhsOnes] = widenBitwiseBounds(bound: argRanges[0]);
571 auto [rhsZeros, rhsOnes] = widenBitwiseBounds(bound: argRanges[1]);
572 auto andi = [](const APInt &a, const APInt &b) -> std::optional<APInt> {
573 return a & b;
574 };
575 std::array<APInt, 2> lhsBounds = {std::move(lhsZeros), std::move(lhsOnes)};
576 std::array<APInt, 2> rhsBounds = {std::move(rhsZeros), std::move(rhsOnes)};
577 return minMaxBy(op: andi, lhs: lhsBounds, rhs: rhsBounds, /*isSigned=*/false);
578}
579
580ConstantIntRanges
581mlir::intrange::inferOr(ArrayRef<ConstantIntRanges> argRanges) {
582 auto [lhsZeros, lhsOnes] = widenBitwiseBounds(bound: argRanges[0]);
583 auto [rhsZeros, rhsOnes] = widenBitwiseBounds(bound: argRanges[1]);
584 auto ori = [](const APInt &a, const APInt &b) -> std::optional<APInt> {
585 return a | b;
586 };
587 std::array<APInt, 2> lhsBounds = {std::move(lhsZeros), std::move(lhsOnes)};
588 std::array<APInt, 2> rhsBounds = {std::move(rhsZeros), std::move(rhsOnes)};
589 return minMaxBy(op: ori, lhs: lhsBounds, rhs: rhsBounds, /*isSigned=*/false);
590}
591
592/// Get bitmask of all bits which can change while iterating in
593/// [bound.umin(), bound.umax()].
594static APInt getVaryingBitsMask(const ConstantIntRanges &bound) {
595 APInt leftVal = bound.umin(), rightVal = bound.umax();
596 unsigned bitwidth = leftVal.getBitWidth();
597 unsigned differingBits =
598 bitwidth - (std::move(leftVal) ^ rightVal).countl_zero();
599 return APInt::getLowBitsSet(numBits: bitwidth, loBitsSet: differingBits);
600}
601
602ConstantIntRanges
603mlir::intrange::inferXor(ArrayRef<ConstantIntRanges> argRanges) {
604 // Construct mask of varying bits for both ranges, xor values and then replace
605 // masked bits with 0s and 1s to get min and max values respectively.
606 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
607 APInt mask = getVaryingBitsMask(bound: lhs) | getVaryingBitsMask(bound: rhs);
608 APInt res = lhs.umin() ^ rhs.umin();
609 APInt min = res & ~mask;
610 APInt max = std::move(res) | mask;
611 return ConstantIntRanges::fromUnsigned(umin: min, umax: max);
612}
613
614//===----------------------------------------------------------------------===//
615// Shifts (Shl, ShrS, ShrU)
616//===----------------------------------------------------------------------===//
617
618ConstantIntRanges
619mlir::intrange::inferShl(ArrayRef<ConstantIntRanges> argRanges,
620 OverflowFlags ovfFlags) {
621 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
622 const APInt &rhsUMin = rhs.umin(), &rhsUMax = rhs.umax();
623
624 // The signed/unsigned overflow behavior of shl by `rhs` matches a mul with
625 // 2^rhs.
626 ConstArithStdFn ushl = [=](const APInt &l,
627 const APInt &r) -> std::optional<APInt> {
628 bool overflowed = false;
629 APInt result = any(Val: ovfFlags & OverflowFlags::Nuw)
630 ? l.ushl_sat(RHS: r)
631 : l.ushl_ov(Amt: r, Overflow&: overflowed);
632 return overflowed ? std::optional<APInt>() : result;
633 };
634 ConstArithStdFn sshl = [=](const APInt &l,
635 const APInt &r) -> std::optional<APInt> {
636 bool overflowed = false;
637 APInt result = any(Val: ovfFlags & OverflowFlags::Nsw)
638 ? l.sshl_sat(RHS: r)
639 : l.sshl_ov(Amt: r, Overflow&: overflowed);
640 return overflowed ? std::optional<APInt>() : result;
641 };
642
643 ConstantIntRanges urange =
644 minMaxBy(op: ushl, lhs: {lhs.umin(), lhs.umax()}, rhs: {rhsUMin, rhsUMax},
645 /*isSigned=*/false);
646 ConstantIntRanges srange =
647 minMaxBy(op: sshl, lhs: {lhs.smin(), lhs.smax()}, rhs: {rhsUMin, rhsUMax},
648 /*isSigned=*/true);
649 return urange.intersection(other: srange);
650}
651
652ConstantIntRanges
653mlir::intrange::inferShrS(ArrayRef<ConstantIntRanges> argRanges) {
654 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
655
656 auto ashr = [](const APInt &l, const APInt &r) -> std::optional<APInt> {
657 return r.uge(RHS: r.getBitWidth()) ? std::optional<APInt>() : l.ashr(ShiftAmt: r);
658 };
659
660 return minMaxBy(op: ashr, lhs: {lhs.smin(), lhs.smax()}, rhs: {rhs.umin(), rhs.umax()},
661 /*isSigned=*/true);
662}
663
664ConstantIntRanges
665mlir::intrange::inferShrU(ArrayRef<ConstantIntRanges> argRanges) {
666 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
667
668 auto lshr = [](const APInt &l, const APInt &r) -> std::optional<APInt> {
669 return r.uge(RHS: r.getBitWidth()) ? std::optional<APInt>() : l.lshr(ShiftAmt: r);
670 };
671 return minMaxBy(op: lshr, lhs: {lhs.umin(), lhs.umax()}, rhs: {rhs.umin(), rhs.umax()},
672 /*isSigned=*/false);
673}
674
675//===----------------------------------------------------------------------===//
676// Comparisons (Cmp)
677//===----------------------------------------------------------------------===//
678
679static intrange::CmpPredicate invertPredicate(intrange::CmpPredicate pred) {
680 switch (pred) {
681 case intrange::CmpPredicate::eq:
682 return intrange::CmpPredicate::ne;
683 case intrange::CmpPredicate::ne:
684 return intrange::CmpPredicate::eq;
685 case intrange::CmpPredicate::slt:
686 return intrange::CmpPredicate::sge;
687 case intrange::CmpPredicate::sle:
688 return intrange::CmpPredicate::sgt;
689 case intrange::CmpPredicate::sgt:
690 return intrange::CmpPredicate::sle;
691 case intrange::CmpPredicate::sge:
692 return intrange::CmpPredicate::slt;
693 case intrange::CmpPredicate::ult:
694 return intrange::CmpPredicate::uge;
695 case intrange::CmpPredicate::ule:
696 return intrange::CmpPredicate::ugt;
697 case intrange::CmpPredicate::ugt:
698 return intrange::CmpPredicate::ule;
699 case intrange::CmpPredicate::uge:
700 return intrange::CmpPredicate::ult;
701 }
702 llvm_unreachable("unknown cmp predicate value");
703}
704
705static bool isStaticallyTrue(intrange::CmpPredicate pred,
706 const ConstantIntRanges &lhs,
707 const ConstantIntRanges &rhs) {
708 switch (pred) {
709 case intrange::CmpPredicate::sle:
710 return lhs.smax().sle(RHS: rhs.smin());
711 case intrange::CmpPredicate::slt:
712 return lhs.smax().slt(RHS: rhs.smin());
713 case intrange::CmpPredicate::ule:
714 return lhs.umax().ule(RHS: rhs.umin());
715 case intrange::CmpPredicate::ult:
716 return lhs.umax().ult(RHS: rhs.umin());
717 case intrange::CmpPredicate::sge:
718 return lhs.smin().sge(RHS: rhs.smax());
719 case intrange::CmpPredicate::sgt:
720 return lhs.smin().sgt(RHS: rhs.smax());
721 case intrange::CmpPredicate::uge:
722 return lhs.umin().uge(RHS: rhs.umax());
723 case intrange::CmpPredicate::ugt:
724 return lhs.umin().ugt(RHS: rhs.umax());
725 case intrange::CmpPredicate::eq: {
726 std::optional<APInt> lhsConst = lhs.getConstantValue();
727 std::optional<APInt> rhsConst = rhs.getConstantValue();
728 return lhsConst && rhsConst && lhsConst == rhsConst;
729 }
730 case intrange::CmpPredicate::ne: {
731 // While equality requires that there is an interpration of the preceeding
732 // computations that produces equal constants, whether that be signed or
733 // unsigned, statically determining inequality requires that neither
734 // interpretation produce potentially overlapping ranges.
735 bool sne = isStaticallyTrue(pred: intrange::CmpPredicate::slt, lhs, rhs) ||
736 isStaticallyTrue(pred: intrange::CmpPredicate::sgt, lhs, rhs);
737 bool une = isStaticallyTrue(pred: intrange::CmpPredicate::ult, lhs, rhs) ||
738 isStaticallyTrue(pred: intrange::CmpPredicate::ugt, lhs, rhs);
739 return sne && une;
740 }
741 }
742 return false;
743}
744
745std::optional<bool> mlir::intrange::evaluatePred(CmpPredicate pred,
746 const ConstantIntRanges &lhs,
747 const ConstantIntRanges &rhs) {
748 if (isStaticallyTrue(pred, lhs, rhs))
749 return true;
750 if (isStaticallyTrue(pred: invertPredicate(pred), lhs, rhs))
751 return false;
752 return std::nullopt;
753}
754
755//===----------------------------------------------------------------------===//
756// Shaped type dimension accessors / ShapedDimOpInterface
757//===----------------------------------------------------------------------===//
758
759ConstantIntRanges
760mlir::intrange::inferShapedDimOpInterface(ShapedDimOpInterface op,
761 const IntegerValueRange &maybeDim) {
762 unsigned width =
763 ConstantIntRanges::getStorageBitwidth(type: op->getResult(idx: 0).getType());
764 APInt zero = APInt::getZero(numBits: width);
765 APInt typeMax = APInt::getSignedMaxValue(numBits: width);
766
767 auto shapedTy = cast<ShapedType>(Val: op.getShapedValue().getType());
768 if (!shapedTy.hasRank())
769 return ConstantIntRanges::fromSigned(smin: zero, smax: typeMax);
770
771 int64_t rank = shapedTy.getRank();
772 int64_t minDim = 0;
773 int64_t maxDim = rank - 1;
774 if (!maybeDim.isUninitialized()) {
775 const ConstantIntRanges &dim = maybeDim.getValue();
776 minDim = std::max(a: minDim, b: dim.smin().getSExtValue());
777 maxDim = std::min(a: maxDim, b: dim.smax().getSExtValue());
778 }
779
780 std::optional<ConstantIntRanges> result;
781 auto joinResult = [&](const ConstantIntRanges &thisResult) {
782 if (!result.has_value())
783 result = thisResult;
784 else
785 result = result->rangeUnion(other: thisResult);
786 };
787 for (int64_t i = minDim; i <= maxDim; ++i) {
788 int64_t length = shapedTy.getDimSize(idx: i);
789
790 if (ShapedType::isDynamic(dValue: length))
791 joinResult(ConstantIntRanges::fromSigned(smin: zero, smax: typeMax));
792 else
793 joinResult(ConstantIntRanges::constant(value: APInt(width, length)));
794 }
795 return result.value_or(u: ConstantIntRanges::fromSigned(smin: zero, smax: typeMax));
796}
797
798//===----------------------------------------------------------------------===//
799// Affine expression inference
800//===----------------------------------------------------------------------===//
801
802static ConstantIntRanges clampToPositive(const ConstantIntRanges &val) {
803 unsigned width = val.smin().getBitWidth();
804 APInt one(width, 1);
805 APInt clampedUMin = val.umin().ult(RHS: one) ? one : val.umin();
806 APInt clampedSMin = val.smin().slt(RHS: one) ? one : val.smin();
807 return ConstantIntRanges::fromUnsigned(umin: clampedUMin, umax: val.umax())
808 .intersection(other: ConstantIntRanges::fromSigned(smin: clampedSMin, smax: val.smax()));
809}
810
811ConstantIntRanges
812mlir::intrange::inferAffineExpr(AffineExpr expr,
813 ArrayRef<ConstantIntRanges> dimRanges,
814 ArrayRef<ConstantIntRanges> symbolRanges) {
815 switch (expr.getKind()) {
816 case AffineExprKind::Constant: {
817 auto constExpr = cast<AffineConstantExpr>(Val&: expr);
818 APInt value(indexMaxWidth, constExpr.getValue(), /*isSigned=*/true);
819 return ConstantIntRanges::constant(value);
820 }
821 case AffineExprKind::DimId: {
822 auto dimExpr = cast<AffineDimExpr>(Val&: expr);
823 unsigned pos = dimExpr.getPosition();
824 assert(pos < dimRanges.size() && "Dimension index out of bounds");
825 return dimRanges[pos];
826 }
827 case AffineExprKind::SymbolId: {
828 auto symbolExpr = cast<AffineSymbolExpr>(Val&: expr);
829 unsigned pos = symbolExpr.getPosition();
830 assert(pos < symbolRanges.size() && "Symbol index out of bounds");
831 return symbolRanges[pos];
832 }
833 case AffineExprKind::Add: {
834 auto binExpr = cast<AffineBinaryOpExpr>(Val&: expr);
835 ConstantIntRanges lhs =
836 inferAffineExpr(expr: binExpr.getLHS(), dimRanges, symbolRanges);
837 ConstantIntRanges rhs =
838 inferAffineExpr(expr: binExpr.getRHS(), dimRanges, symbolRanges);
839 std::array<ConstantIntRanges, 2> operands = {std::move(lhs),
840 std::move(rhs)};
841 return inferAdd(argRanges: operands, ovfFlags: OverflowFlags::Nsw);
842 }
843 case AffineExprKind::Mul: {
844 auto binExpr = cast<AffineBinaryOpExpr>(Val&: expr);
845 ConstantIntRanges lhs =
846 inferAffineExpr(expr: binExpr.getLHS(), dimRanges, symbolRanges);
847 ConstantIntRanges rhs =
848 inferAffineExpr(expr: binExpr.getRHS(), dimRanges, symbolRanges);
849 std::array<ConstantIntRanges, 2> operands = {std::move(lhs),
850 std::move(rhs)};
851 return inferMul(argRanges: operands, ovfFlags: OverflowFlags::Nsw);
852 }
853 case AffineExprKind::Mod: {
854 auto binExpr = cast<AffineBinaryOpExpr>(Val&: expr);
855 ConstantIntRanges lhs =
856 inferAffineExpr(expr: binExpr.getLHS(), dimRanges, symbolRanges);
857 ConstantIntRanges rhs =
858 inferAffineExpr(expr: binExpr.getRHS(), dimRanges, symbolRanges);
859 // Affine mod is Euclidean modulo: result is always in [0, rhs-1].
860 // This assumes RHS is positive (enforced by affine expr semantics).
861 const APInt &lhsMin = lhs.smin();
862 const APInt &lhsMax = lhs.smax();
863 const APInt &rhsMin = rhs.smin();
864 const APInt &rhsMax = rhs.smax();
865 unsigned width = rhsMin.getBitWidth();
866
867 // Guard against division by zero.
868 if (rhsMax.isZero())
869 return ConstantIntRanges::maxRange(bitwidth: width);
870
871 // For Euclidean mod, result is in [0, max(rhs)-1].
872 APInt umin = APInt::getZero(numBits: width);
873 APInt umax = rhsMax - 1;
874
875 // Special case: if dividend is already in [0, min(rhs)), result equals
876 // dividend. We use rhsMin to ensure this is safe for all possible divisor
877 // values.
878 if (rhsMin.isStrictlyPositive() && lhsMin.isNonNegative() &&
879 lhsMax.ult(RHS: rhsMin)) {
880 umin = lhsMin;
881 umax = lhsMax;
882 }
883 // Special case: sweeping out a contiguous range with constant divisor.
884 // Only applies when dividend is non-negative and the range does not
885 // cross a modulus boundary (same quotient), ensuring contiguity.
886 else if (rhsMin == rhsMax && lhsMin.isNonNegative() &&
887 (lhsMax - lhsMin).ult(RHS: rhsMax) &&
888 lhsMin.udiv(RHS: rhsMax) == lhsMax.udiv(RHS: rhsMax)) {
889 // For non-negative dividends within the same modular period,
890 // Euclidean mod is same as unsigned remainder and the result is
891 // contiguous.
892 umin = lhsMin.urem(RHS: rhsMax);
893 umax = lhsMax.urem(RHS: rhsMax);
894 // Result should be contiguous since we're not wrapping around.
895 assert(umin.ule(umax) &&
896 "Range should be contiguous for non-negative dividend");
897 }
898
899 return ConstantIntRanges::fromUnsigned(umin, umax);
900 }
901 case AffineExprKind::FloorDiv: {
902 auto binExpr = cast<AffineBinaryOpExpr>(Val&: expr);
903 ConstantIntRanges lhs =
904 inferAffineExpr(expr: binExpr.getLHS(), dimRanges, symbolRanges);
905 ConstantIntRanges rhs =
906 inferAffineExpr(expr: binExpr.getRHS(), dimRanges, symbolRanges);
907 // Affine floordiv requires strictly positive divisor (> 0).
908 // Clamp divisor lower bound to 1 for tighter range inference.
909 ConstantIntRanges clampedRhs = clampToPositive(val: rhs);
910 std::array<ConstantIntRanges, 2> operands = {std::move(lhs),
911 std::move(clampedRhs)};
912 return inferFloorDivS(argRanges: operands);
913 }
914 case AffineExprKind::CeilDiv: {
915 auto binExpr = cast<AffineBinaryOpExpr>(Val&: expr);
916 ConstantIntRanges lhs =
917 inferAffineExpr(expr: binExpr.getLHS(), dimRanges, symbolRanges);
918 ConstantIntRanges rhs =
919 inferAffineExpr(expr: binExpr.getRHS(), dimRanges, symbolRanges);
920 // Affine ceildiv requires strictly positive divisor (> 0).
921 // Clamp divisor lower bound to 1 for tighter range inference.
922 ConstantIntRanges clampedRhs = clampToPositive(val: rhs);
923 std::array<ConstantIntRanges, 2> operands = {std::move(lhs),
924 std::move(clampedRhs)};
925 return inferCeilDivS(argRanges: operands);
926 }
927 }
928 llvm_unreachable("unknown affine expression kind");
929}
930