xref: /llvm-project/mlir/lib/Interfaces/Utils/InferIntRangeCommon.cpp (revision 2e612f8d868b3fb88a44964a3d4efd61ee63e06a) 
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/Interfaces/InferIntRangeInterface.h"
17 
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/ADT/STLExtras.h"
20 
21 #include "llvm/Support/Debug.h"
22 
23 #include <iterator>
24 #include <optional>
25 
26 using namespace mlir;
27 
28 #define DEBUG_TYPE "int-range-analysis"
29 
30 //===----------------------------------------------------------------------===//
31 // General utilities
32 //===----------------------------------------------------------------------===//
33 
34 /// Function that evaluates the result of doing something on arithmetic
35 /// constants and returns std::nullopt on overflow.
36 using ConstArithFn =
37     function_ref<std::optional<APInt>(const APInt &, const APInt &)>;
38 using ConstArithStdFn =
39     std::function<std::optional<APInt>(const APInt &, const APInt &)>;
40 
41 /// Compute op(minLeft, minRight) and op(maxLeft, maxRight) if possible,
42 /// If either computation overflows, make the result unbounded.
43 static ConstantIntRanges computeBoundsBy(ConstArithFn op, const APInt &minLeft,
44                                          const APInt &minRight,
45                                          const APInt &maxLeft,
46                                          const APInt &maxRight, bool isSigned) {
47   std::optional<APInt> maybeMin = op(minLeft, minRight);
48   std::optional<APInt> maybeMax = op(maxLeft, maxRight);
49   if (maybeMin && maybeMax)
50     return ConstantIntRanges::range(*maybeMin, *maybeMax, isSigned);
51   return ConstantIntRanges::maxRange(minLeft.getBitWidth());
52 }
53 
54 /// Compute the minimum and maximum of `(op(l, r) for l in lhs for r in rhs)`,
55 /// ignoring unbounded values. Returns the maximal range if `op` overflows.
56 static ConstantIntRanges minMaxBy(ConstArithFn op, ArrayRef<APInt> lhs,
57                                   ArrayRef<APInt> rhs, bool isSigned) {
58   unsigned width = lhs[0].getBitWidth();
59   APInt min =
60       isSigned ? APInt::getSignedMaxValue(width) : APInt::getMaxValue(width);
61   APInt max =
62       isSigned ? APInt::getSignedMinValue(width) : APInt::getZero(width);
63   for (const APInt &left : lhs) {
64     for (const APInt &right : rhs) {
65       std::optional<APInt> maybeThisResult = op(left, right);
66       if (!maybeThisResult)
67         return ConstantIntRanges::maxRange(width);
68       APInt result = std::move(*maybeThisResult);
69       min = (isSigned ? result.slt(min) : result.ult(min)) ? result : min;
70       max = (isSigned ? result.sgt(max) : result.ugt(max)) ? result : max;
71     }
72   }
73   return ConstantIntRanges::range(min, max, isSigned);
74 }
75 
76 //===----------------------------------------------------------------------===//
77 // Ext, trunc, index op handling
78 //===----------------------------------------------------------------------===//
79 
80 ConstantIntRanges
81 mlir::intrange::inferIndexOp(const InferRangeFn &inferFn,
82                              ArrayRef<ConstantIntRanges> argRanges,
83                              intrange::CmpMode mode) {
84   ConstantIntRanges sixtyFour = inferFn(argRanges);
85   SmallVector<ConstantIntRanges, 2> truncated;
86   llvm::transform(argRanges, std::back_inserter(truncated),
87                   [](const ConstantIntRanges &range) {
88                     return truncRange(range, /*destWidth=*/indexMinWidth);
89                   });
90   ConstantIntRanges thirtyTwo = inferFn(truncated);
91   ConstantIntRanges thirtyTwoAsSixtyFour =
92       extRange(thirtyTwo, /*destWidth=*/indexMaxWidth);
93   ConstantIntRanges sixtyFourAsThirtyTwo =
94       truncRange(sixtyFour, /*destWidth=*/indexMinWidth);
95 
96   LLVM_DEBUG(llvm::dbgs() << "Index handling: 64-bit result = " << sixtyFour
97                           << " 32-bit = " << thirtyTwo << "\n");
98   bool truncEqual = false;
99   switch (mode) {
100   case intrange::CmpMode::Both:
101     truncEqual = (thirtyTwo == sixtyFourAsThirtyTwo);
102     break;
103   case intrange::CmpMode::Signed:
104     truncEqual = (thirtyTwo.smin() == sixtyFourAsThirtyTwo.smin() &&
105                   thirtyTwo.smax() == sixtyFourAsThirtyTwo.smax());
106     break;
107   case intrange::CmpMode::Unsigned:
108     truncEqual = (thirtyTwo.umin() == sixtyFourAsThirtyTwo.umin() &&
109                   thirtyTwo.umax() == sixtyFourAsThirtyTwo.umax());
110     break;
111   }
112   if (truncEqual)
113     // Returing the 64-bit result preserves more information.
114     return sixtyFour;
115   ConstantIntRanges merged = sixtyFour.rangeUnion(thirtyTwoAsSixtyFour);
116   return merged;
117 }
118 
119 ConstantIntRanges mlir::intrange::extRange(const ConstantIntRanges &range,
120                                            unsigned int destWidth) {
121   APInt umin = range.umin().zext(destWidth);
122   APInt umax = range.umax().zext(destWidth);
123   APInt smin = range.smin().sext(destWidth);
124   APInt smax = range.smax().sext(destWidth);
125   return {umin, umax, smin, smax};
126 }
127 
128 ConstantIntRanges mlir::intrange::extUIRange(const ConstantIntRanges &range,
129                                              unsigned destWidth) {
130   APInt umin = range.umin().zext(destWidth);
131   APInt umax = range.umax().zext(destWidth);
132   return ConstantIntRanges::fromUnsigned(umin, umax);
133 }
134 
135 ConstantIntRanges mlir::intrange::extSIRange(const ConstantIntRanges &range,
136                                              unsigned destWidth) {
137   APInt smin = range.smin().sext(destWidth);
138   APInt smax = range.smax().sext(destWidth);
139   return ConstantIntRanges::fromSigned(smin, smax);
140 }
141 
142 ConstantIntRanges mlir::intrange::truncRange(const ConstantIntRanges &range,
143                                              unsigned int destWidth) {
144   // If you truncate the first four bytes in [0xaaaabbbb, 0xccccbbbb],
145   // the range of the resulting value is not contiguous ind includes 0.
146   // Ex. If you truncate [256, 258] from i16 to i8, you validly get [0, 2],
147   // but you can't truncate [255, 257] similarly.
148   bool hasUnsignedRollover =
149       range.umin().lshr(destWidth) != range.umax().lshr(destWidth);
150   APInt umin = hasUnsignedRollover ? APInt::getZero(destWidth)
151                                    : range.umin().trunc(destWidth);
152   APInt umax = hasUnsignedRollover ? APInt::getMaxValue(destWidth)
153                                    : range.umax().trunc(destWidth);
154 
155   // Signed post-truncation rollover will not occur when either:
156   // - The high parts of the min and max, plus the sign bit, are the same
157   // - The high halves + sign bit of the min and max are either all 1s or all 0s
158   //  and you won't create a [positive, negative] range by truncating.
159   // For example, you can truncate the ranges [256, 258]_i16 to [0, 2]_i8
160   // but not [255, 257]_i16 to a range of i8s. You can also truncate
161   // [-256, -256]_i16 to [-2, 0]_i8, but not [-257, -255]_i16.
162   // You can also truncate [-130, 0]_i16 to i8 because -130_i16 (0xff7e)
163   // will truncate to 0x7e, which is greater than 0
164   APInt sminHighPart = range.smin().ashr(destWidth - 1);
165   APInt smaxHighPart = range.smax().ashr(destWidth - 1);
166   bool hasSignedOverflow =
167       (sminHighPart != smaxHighPart) &&
168       !(sminHighPart.isAllOnes() &&
169         (smaxHighPart.isAllOnes() || smaxHighPart.isZero())) &&
170       !(sminHighPart.isZero() && smaxHighPart.isZero());
171   APInt smin = hasSignedOverflow ? APInt::getSignedMinValue(destWidth)
172                                  : range.smin().trunc(destWidth);
173   APInt smax = hasSignedOverflow ? APInt::getSignedMaxValue(destWidth)
174                                  : range.smax().trunc(destWidth);
175   return {umin, umax, smin, smax};
176 }
177 
178 //===----------------------------------------------------------------------===//
179 // Addition
180 //===----------------------------------------------------------------------===//
181 
182 ConstantIntRanges
183 mlir::intrange::inferAdd(ArrayRef<ConstantIntRanges> argRanges,
184                          OverflowFlags ovfFlags) {
185   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
186 
187   ConstArithStdFn uadd = [=](const APInt &a,
188                              const APInt &b) -> std::optional<APInt> {
189     bool overflowed = false;
190     APInt result = any(ovfFlags & OverflowFlags::Nuw)
191                        ? a.uadd_sat(b)
192                        : a.uadd_ov(b, overflowed);
193     return overflowed ? std::optional<APInt>() : result;
194   };
195   ConstArithStdFn sadd = [=](const APInt &a,
196                              const APInt &b) -> std::optional<APInt> {
197     bool overflowed = false;
198     APInt result = any(ovfFlags & OverflowFlags::Nsw)
199                        ? a.sadd_sat(b)
200                        : a.sadd_ov(b, overflowed);
201     return overflowed ? std::optional<APInt>() : result;
202   };
203 
204   ConstantIntRanges urange = computeBoundsBy(
205       uadd, lhs.umin(), rhs.umin(), lhs.umax(), rhs.umax(), /*isSigned=*/false);
206   ConstantIntRanges srange = computeBoundsBy(
207       sadd, lhs.smin(), rhs.smin(), lhs.smax(), rhs.smax(), /*isSigned=*/true);
208   return urange.intersection(srange);
209 }
210 
211 //===----------------------------------------------------------------------===//
212 // Subtraction
213 //===----------------------------------------------------------------------===//
214 
215 ConstantIntRanges
216 mlir::intrange::inferSub(ArrayRef<ConstantIntRanges> argRanges,
217                          OverflowFlags ovfFlags) {
218   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
219 
220   ConstArithStdFn usub = [=](const APInt &a,
221                              const APInt &b) -> std::optional<APInt> {
222     bool overflowed = false;
223     APInt result = any(ovfFlags & OverflowFlags::Nuw)
224                        ? a.usub_sat(b)
225                        : a.usub_ov(b, overflowed);
226     return overflowed ? std::optional<APInt>() : result;
227   };
228   ConstArithStdFn ssub = [=](const APInt &a,
229                              const APInt &b) -> std::optional<APInt> {
230     bool overflowed = false;
231     APInt result = any(ovfFlags & OverflowFlags::Nsw)
232                        ? a.ssub_sat(b)
233                        : a.ssub_ov(b, overflowed);
234     return overflowed ? std::optional<APInt>() : result;
235   };
236   ConstantIntRanges urange = computeBoundsBy(
237       usub, lhs.umin(), rhs.umax(), lhs.umax(), rhs.umin(), /*isSigned=*/false);
238   ConstantIntRanges srange = computeBoundsBy(
239       ssub, lhs.smin(), rhs.smax(), lhs.smax(), rhs.smin(), /*isSigned=*/true);
240   return urange.intersection(srange);
241 }
242 
243 //===----------------------------------------------------------------------===//
244 // Multiplication
245 //===----------------------------------------------------------------------===//
246 
247 ConstantIntRanges
248 mlir::intrange::inferMul(ArrayRef<ConstantIntRanges> argRanges,
249                          OverflowFlags ovfFlags) {
250   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
251 
252   ConstArithStdFn umul = [=](const APInt &a,
253                              const APInt &b) -> std::optional<APInt> {
254     bool overflowed = false;
255     APInt result = any(ovfFlags & OverflowFlags::Nuw)
256                        ? a.umul_sat(b)
257                        : a.umul_ov(b, overflowed);
258     return overflowed ? std::optional<APInt>() : result;
259   };
260   ConstArithStdFn smul = [=](const APInt &a,
261                              const APInt &b) -> std::optional<APInt> {
262     bool overflowed = false;
263     APInt result = any(ovfFlags & OverflowFlags::Nsw)
264                        ? a.smul_sat(b)
265                        : a.smul_ov(b, overflowed);
266     return overflowed ? std::optional<APInt>() : result;
267   };
268 
269   ConstantIntRanges urange =
270       minMaxBy(umul, {lhs.umin(), lhs.umax()}, {rhs.umin(), rhs.umax()},
271                /*isSigned=*/false);
272   ConstantIntRanges srange =
273       minMaxBy(smul, {lhs.smin(), lhs.smax()}, {rhs.smin(), rhs.smax()},
274                /*isSigned=*/true);
275   return urange.intersection(srange);
276 }
277 
278 //===----------------------------------------------------------------------===//
279 // DivU, CeilDivU (Unsigned division)
280 //===----------------------------------------------------------------------===//
281 
282 /// Fix up division results (ex. for ceiling and floor), returning an APInt
283 /// if there has been no overflow
284 using DivisionFixupFn = function_ref<std::optional<APInt>(
285     const APInt &lhs, const APInt &rhs, const APInt &result)>;
286 
287 static ConstantIntRanges inferDivURange(const ConstantIntRanges &lhs,
288                                         const ConstantIntRanges &rhs,
289                                         DivisionFixupFn fixup) {
290   const APInt &lhsMin = lhs.umin(), &lhsMax = lhs.umax(), &rhsMin = rhs.umin(),
291               &rhsMax = rhs.umax();
292 
293   if (!rhsMin.isZero()) {
294     auto udiv = [&fixup](const APInt &a,
295                          const APInt &b) -> std::optional<APInt> {
296       return fixup(a, b, a.udiv(b));
297     };
298     return minMaxBy(udiv, {lhsMin, lhsMax}, {rhsMin, rhsMax},
299                     /*isSigned=*/false);
300   }
301 
302   APInt umin = APInt::getZero(rhsMin.getBitWidth());
303   if (lhsMin.uge(rhsMax) && !rhsMax.isZero())
304     umin = lhsMin.udiv(rhsMax);
305 
306   // X u/ Y u<= X.
307   APInt umax = lhsMax;
308   return ConstantIntRanges::fromUnsigned(umin, umax);
309 }
310 
311 ConstantIntRanges
312 mlir::intrange::inferDivU(ArrayRef<ConstantIntRanges> argRanges) {
313   return inferDivURange(argRanges[0], argRanges[1],
314                         [](const APInt &lhs, const APInt &rhs,
315                            const APInt &result) { return result; });
316 }
317 
318 ConstantIntRanges
319 mlir::intrange::inferCeilDivU(ArrayRef<ConstantIntRanges> argRanges) {
320   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
321 
322   DivisionFixupFn ceilDivUIFix =
323       [](const APInt &lhs, const APInt &rhs,
324          const APInt &result) -> std::optional<APInt> {
325     if (!lhs.urem(rhs).isZero()) {
326       bool overflowed = false;
327       APInt corrected =
328           result.uadd_ov(APInt(result.getBitWidth(), 1), overflowed);
329       return overflowed ? std::optional<APInt>() : corrected;
330     }
331     return result;
332   };
333   return inferDivURange(lhs, rhs, ceilDivUIFix);
334 }
335 
336 //===----------------------------------------------------------------------===//
337 // DivS, CeilDivS, FloorDivS (Signed division)
338 //===----------------------------------------------------------------------===//
339 
340 static ConstantIntRanges inferDivSRange(const ConstantIntRanges &lhs,
341                                         const ConstantIntRanges &rhs,
342                                         DivisionFixupFn fixup) {
343   const APInt &lhsMin = lhs.smin(), &lhsMax = lhs.smax(), &rhsMin = rhs.smin(),
344               &rhsMax = rhs.smax();
345   bool canDivide = rhsMin.isStrictlyPositive() || rhsMax.isNegative();
346 
347   if (canDivide) {
348     auto sdiv = [&fixup](const APInt &a,
349                          const APInt &b) -> std::optional<APInt> {
350       bool overflowed = false;
351       APInt result = a.sdiv_ov(b, overflowed);
352       return overflowed ? std::optional<APInt>() : fixup(a, b, result);
353     };
354     return minMaxBy(sdiv, {lhsMin, lhsMax}, {rhsMin, rhsMax},
355                     /*isSigned=*/true);
356   }
357   return ConstantIntRanges::maxRange(rhsMin.getBitWidth());
358 }
359 
360 ConstantIntRanges
361 mlir::intrange::inferDivS(ArrayRef<ConstantIntRanges> argRanges) {
362   return inferDivSRange(argRanges[0], argRanges[1],
363                         [](const APInt &lhs, const APInt &rhs,
364                            const APInt &result) { return result; });
365 }
366 
367 ConstantIntRanges
368 mlir::intrange::inferCeilDivS(ArrayRef<ConstantIntRanges> argRanges) {
369   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
370 
371   DivisionFixupFn ceilDivSIFix =
372       [](const APInt &lhs, const APInt &rhs,
373          const APInt &result) -> std::optional<APInt> {
374     if (!lhs.srem(rhs).isZero() && lhs.isNonNegative() == rhs.isNonNegative()) {
375       bool overflowed = false;
376       APInt corrected =
377           result.sadd_ov(APInt(result.getBitWidth(), 1), overflowed);
378       return overflowed ? std::optional<APInt>() : corrected;
379     }
380     return result;
381   };
382   return inferDivSRange(lhs, rhs, ceilDivSIFix);
383 }
384 
385 ConstantIntRanges
386 mlir::intrange::inferFloorDivS(ArrayRef<ConstantIntRanges> argRanges) {
387   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
388 
389   DivisionFixupFn floorDivSIFix =
390       [](const APInt &lhs, const APInt &rhs,
391          const APInt &result) -> std::optional<APInt> {
392     if (!lhs.srem(rhs).isZero() && lhs.isNonNegative() != rhs.isNonNegative()) {
393       bool overflowed = false;
394       APInt corrected =
395           result.ssub_ov(APInt(result.getBitWidth(), 1), overflowed);
396       return overflowed ? std::optional<APInt>() : corrected;
397     }
398     return result;
399   };
400   return inferDivSRange(lhs, rhs, floorDivSIFix);
401 }
402 
403 //===----------------------------------------------------------------------===//
404 // Signed remainder (RemS)
405 //===----------------------------------------------------------------------===//
406 
407 ConstantIntRanges
408 mlir::intrange::inferRemS(ArrayRef<ConstantIntRanges> argRanges) {
409   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
410   const APInt &lhsMin = lhs.smin(), &lhsMax = lhs.smax(), &rhsMin = rhs.smin(),
411               &rhsMax = rhs.smax();
412 
413   unsigned width = rhsMax.getBitWidth();
414   APInt smin = APInt::getSignedMinValue(width);
415   APInt smax = APInt::getSignedMaxValue(width);
416   // No bounds if zero could be a divisor.
417   bool canBound = (rhsMin.isStrictlyPositive() || rhsMax.isNegative());
418   if (canBound) {
419     APInt maxDivisor = rhsMin.isStrictlyPositive() ? rhsMax : rhsMin.abs();
420     bool canNegativeDividend = lhsMin.isNegative();
421     bool canPositiveDividend = lhsMax.isStrictlyPositive();
422     APInt zero = APInt::getZero(maxDivisor.getBitWidth());
423     APInt maxPositiveResult = maxDivisor - 1;
424     APInt minNegativeResult = -maxPositiveResult;
425     smin = canNegativeDividend ? minNegativeResult : zero;
426     smax = canPositiveDividend ? maxPositiveResult : zero;
427     // Special case: sweeping out a contiguous range in N/[modulus].
428     if (rhsMin == rhsMax) {
429       if ((lhsMax - lhsMin).ult(maxDivisor)) {
430         APInt minRem = lhsMin.srem(maxDivisor);
431         APInt maxRem = lhsMax.srem(maxDivisor);
432         if (minRem.sle(maxRem)) {
433           smin = minRem;
434           smax = maxRem;
435         }
436       }
437     }
438   }
439   return ConstantIntRanges::fromSigned(smin, smax);
440 }
441 
442 //===----------------------------------------------------------------------===//
443 // Unsigned remainder (RemU)
444 //===----------------------------------------------------------------------===//
445 
446 ConstantIntRanges
447 mlir::intrange::inferRemU(ArrayRef<ConstantIntRanges> argRanges) {
448   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
449   const APInt &rhsMin = rhs.umin(), &rhsMax = rhs.umax();
450 
451   unsigned width = rhsMin.getBitWidth();
452   APInt umin = APInt::getZero(width);
453   // Remainder can't be larger than either of its arguments.
454   APInt umax = llvm::APIntOps::umin((rhsMax - 1), lhs.umax());
455 
456   if (!rhsMin.isZero()) {
457     // Special case: sweeping out a contiguous range in N/[modulus]
458     if (rhsMin == rhsMax) {
459       const APInt &lhsMin = lhs.umin(), &lhsMax = lhs.umax();
460       if ((lhsMax - lhsMin).ult(rhsMax)) {
461         APInt minRem = lhsMin.urem(rhsMax);
462         APInt maxRem = lhsMax.urem(rhsMax);
463         if (minRem.ule(maxRem)) {
464           umin = minRem;
465           umax = maxRem;
466         }
467       }
468     }
469   }
470   return ConstantIntRanges::fromUnsigned(umin, umax);
471 }
472 
473 //===----------------------------------------------------------------------===//
474 // Max and min (MaxS, MaxU, MinS, MinU)
475 //===----------------------------------------------------------------------===//
476 
477 ConstantIntRanges
478 mlir::intrange::inferMaxS(ArrayRef<ConstantIntRanges> argRanges) {
479   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
480 
481   const APInt &smin = lhs.smin().sgt(rhs.smin()) ? lhs.smin() : rhs.smin();
482   const APInt &smax = lhs.smax().sgt(rhs.smax()) ? lhs.smax() : rhs.smax();
483   return ConstantIntRanges::fromSigned(smin, smax);
484 }
485 
486 ConstantIntRanges
487 mlir::intrange::inferMaxU(ArrayRef<ConstantIntRanges> argRanges) {
488   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
489 
490   const APInt &umin = lhs.umin().ugt(rhs.umin()) ? lhs.umin() : rhs.umin();
491   const APInt &umax = lhs.umax().ugt(rhs.umax()) ? lhs.umax() : rhs.umax();
492   return ConstantIntRanges::fromUnsigned(umin, umax);
493 }
494 
495 ConstantIntRanges
496 mlir::intrange::inferMinS(ArrayRef<ConstantIntRanges> argRanges) {
497   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
498 
499   const APInt &smin = lhs.smin().slt(rhs.smin()) ? lhs.smin() : rhs.smin();
500   const APInt &smax = lhs.smax().slt(rhs.smax()) ? lhs.smax() : rhs.smax();
501   return ConstantIntRanges::fromSigned(smin, smax);
502 }
503 
504 ConstantIntRanges
505 mlir::intrange::inferMinU(ArrayRef<ConstantIntRanges> argRanges) {
506   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
507 
508   const APInt &umin = lhs.umin().ult(rhs.umin()) ? lhs.umin() : rhs.umin();
509   const APInt &umax = lhs.umax().ult(rhs.umax()) ? lhs.umax() : rhs.umax();
510   return ConstantIntRanges::fromUnsigned(umin, umax);
511 }
512 
513 //===----------------------------------------------------------------------===//
514 // Bitwise operators (And, Or, Xor)
515 //===----------------------------------------------------------------------===//
516 
517 /// "Widen" bounds - if 0bvvvvv??? <= a <= 0bvvvvv???,
518 /// relax the bounds to 0bvvvvv000 <= a <= 0bvvvvv111, where vvvvv are the bits
519 /// that both bonuds have in common. This gives us a consertive approximation
520 /// for what values can be passed to bitwise operations.
521 static std::tuple<APInt, APInt>
522 widenBitwiseBounds(const ConstantIntRanges &bound) {
523   APInt leftVal = bound.umin(), rightVal = bound.umax();
524   unsigned bitwidth = leftVal.getBitWidth();
525   unsigned differingBits = bitwidth - (leftVal ^ rightVal).countl_zero();
526   leftVal.clearLowBits(differingBits);
527   rightVal.setLowBits(differingBits);
528   return std::make_tuple(std::move(leftVal), std::move(rightVal));
529 }
530 
531 ConstantIntRanges
532 mlir::intrange::inferAnd(ArrayRef<ConstantIntRanges> argRanges) {
533   auto [lhsZeros, lhsOnes] = widenBitwiseBounds(argRanges[0]);
534   auto [rhsZeros, rhsOnes] = widenBitwiseBounds(argRanges[1]);
535   auto andi = [](const APInt &a, const APInt &b) -> std::optional<APInt> {
536     return a & b;
537   };
538   return minMaxBy(andi, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
539                   /*isSigned=*/false);
540 }
541 
542 ConstantIntRanges
543 mlir::intrange::inferOr(ArrayRef<ConstantIntRanges> argRanges) {
544   auto [lhsZeros, lhsOnes] = widenBitwiseBounds(argRanges[0]);
545   auto [rhsZeros, rhsOnes] = widenBitwiseBounds(argRanges[1]);
546   auto ori = [](const APInt &a, const APInt &b) -> std::optional<APInt> {
547     return a | b;
548   };
549   return minMaxBy(ori, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
550                   /*isSigned=*/false);
551 }
552 
553 ConstantIntRanges
554 mlir::intrange::inferXor(ArrayRef<ConstantIntRanges> argRanges) {
555   auto [lhsZeros, lhsOnes] = widenBitwiseBounds(argRanges[0]);
556   auto [rhsZeros, rhsOnes] = widenBitwiseBounds(argRanges[1]);
557   auto xori = [](const APInt &a, const APInt &b) -> std::optional<APInt> {
558     return a ^ b;
559   };
560   return minMaxBy(xori, {lhsZeros, lhsOnes}, {rhsZeros, rhsOnes},
561                   /*isSigned=*/false);
562 }
563 
564 //===----------------------------------------------------------------------===//
565 // Shifts (Shl, ShrS, ShrU)
566 //===----------------------------------------------------------------------===//
567 
568 ConstantIntRanges
569 mlir::intrange::inferShl(ArrayRef<ConstantIntRanges> argRanges,
570                          OverflowFlags ovfFlags) {
571   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
572   const APInt &rhsUMin = rhs.umin(), &rhsUMax = rhs.umax();
573 
574   // The signed/unsigned overflow behavior of shl by `rhs` matches a mul with
575   // 2^rhs.
576   ConstArithStdFn ushl = [=](const APInt &l,
577                              const APInt &r) -> std::optional<APInt> {
578     bool overflowed = false;
579     APInt result = any(ovfFlags & OverflowFlags::Nuw)
580                        ? l.ushl_sat(r)
581                        : l.ushl_ov(r, overflowed);
582     return overflowed ? std::optional<APInt>() : result;
583   };
584   ConstArithStdFn sshl = [=](const APInt &l,
585                              const APInt &r) -> std::optional<APInt> {
586     bool overflowed = false;
587     APInt result = any(ovfFlags & OverflowFlags::Nsw)
588                        ? l.sshl_sat(r)
589                        : l.sshl_ov(r, overflowed);
590     return overflowed ? std::optional<APInt>() : result;
591   };
592 
593   ConstantIntRanges urange =
594       minMaxBy(ushl, {lhs.umin(), lhs.umax()}, {rhsUMin, rhsUMax},
595                /*isSigned=*/false);
596   ConstantIntRanges srange =
597       minMaxBy(sshl, {lhs.smin(), lhs.smax()}, {rhsUMin, rhsUMax},
598                /*isSigned=*/true);
599   return urange.intersection(srange);
600 }
601 
602 ConstantIntRanges
603 mlir::intrange::inferShrS(ArrayRef<ConstantIntRanges> argRanges) {
604   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
605 
606   ConstArithFn ashr = [](const APInt &l,
607                          const APInt &r) -> std::optional<APInt> {
608     return r.uge(r.getBitWidth()) ? std::optional<APInt>() : l.ashr(r);
609   };
610 
611   return minMaxBy(ashr, {lhs.smin(), lhs.smax()}, {rhs.umin(), rhs.umax()},
612                   /*isSigned=*/true);
613 }
614 
615 ConstantIntRanges
616 mlir::intrange::inferShrU(ArrayRef<ConstantIntRanges> argRanges) {
617   const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
618 
619   ConstArithFn lshr = [](const APInt &l,
620                          const APInt &r) -> std::optional<APInt> {
621     return r.uge(r.getBitWidth()) ? std::optional<APInt>() : l.lshr(r);
622   };
623   return minMaxBy(lshr, {lhs.umin(), lhs.umax()}, {rhs.umin(), rhs.umax()},
624                   /*isSigned=*/false);
625 }
626 
627 //===----------------------------------------------------------------------===//
628 // Comparisons (Cmp)
629 //===----------------------------------------------------------------------===//
630 
631 static intrange::CmpPredicate invertPredicate(intrange::CmpPredicate pred) {
632   switch (pred) {
633   case intrange::CmpPredicate::eq:
634     return intrange::CmpPredicate::ne;
635   case intrange::CmpPredicate::ne:
636     return intrange::CmpPredicate::eq;
637   case intrange::CmpPredicate::slt:
638     return intrange::CmpPredicate::sge;
639   case intrange::CmpPredicate::sle:
640     return intrange::CmpPredicate::sgt;
641   case intrange::CmpPredicate::sgt:
642     return intrange::CmpPredicate::sle;
643   case intrange::CmpPredicate::sge:
644     return intrange::CmpPredicate::slt;
645   case intrange::CmpPredicate::ult:
646     return intrange::CmpPredicate::uge;
647   case intrange::CmpPredicate::ule:
648     return intrange::CmpPredicate::ugt;
649   case intrange::CmpPredicate::ugt:
650     return intrange::CmpPredicate::ule;
651   case intrange::CmpPredicate::uge:
652     return intrange::CmpPredicate::ult;
653   }
654   llvm_unreachable("unknown cmp predicate value");
655 }
656 
657 static bool isStaticallyTrue(intrange::CmpPredicate pred,
658                              const ConstantIntRanges &lhs,
659                              const ConstantIntRanges &rhs) {
660   switch (pred) {
661   case intrange::CmpPredicate::sle:
662     return lhs.smax().sle(rhs.smin());
663   case intrange::CmpPredicate::slt:
664     return lhs.smax().slt(rhs.smin());
665   case intrange::CmpPredicate::ule:
666     return lhs.umax().ule(rhs.umin());
667   case intrange::CmpPredicate::ult:
668     return lhs.umax().ult(rhs.umin());
669   case intrange::CmpPredicate::sge:
670     return lhs.smin().sge(rhs.smax());
671   case intrange::CmpPredicate::sgt:
672     return lhs.smin().sgt(rhs.smax());
673   case intrange::CmpPredicate::uge:
674     return lhs.umin().uge(rhs.umax());
675   case intrange::CmpPredicate::ugt:
676     return lhs.umin().ugt(rhs.umax());
677   case intrange::CmpPredicate::eq: {
678     std::optional<APInt> lhsConst = lhs.getConstantValue();
679     std::optional<APInt> rhsConst = rhs.getConstantValue();
680     return lhsConst && rhsConst && lhsConst == rhsConst;
681   }
682   case intrange::CmpPredicate::ne: {
683     // While equality requires that there is an interpration of the preceeding
684     // computations that produces equal constants, whether that be signed or
685     // unsigned, statically determining inequality requires that neither
686     // interpretation produce potentially overlapping ranges.
687     bool sne = isStaticallyTrue(intrange::CmpPredicate::slt, lhs, rhs) ||
688                isStaticallyTrue(intrange::CmpPredicate::sgt, lhs, rhs);
689     bool une = isStaticallyTrue(intrange::CmpPredicate::ult, lhs, rhs) ||
690                isStaticallyTrue(intrange::CmpPredicate::ugt, lhs, rhs);
691     return sne && une;
692   }
693   }
694   return false;
695 }
696 
697 std::optional<bool> mlir::intrange::evaluatePred(CmpPredicate pred,
698                                                  const ConstantIntRanges &lhs,
699                                                  const ConstantIntRanges &rhs) {
700   if (isStaticallyTrue(pred, lhs, rhs))
701     return true;
702   if (isStaticallyTrue(invertPredicate(pred), lhs, rhs))
703     return false;
704   return std::nullopt;
705 }
706