1//===- InferIntRangeInterfaceImpls.cpp - Integer range impls for arith -===//
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#include "mlir/Dialect/Arith/IR/Arith.h"
10#include "mlir/Interfaces/InferIntRangeInterface.h"
11#include "mlir/Interfaces/Utils/InferIntRangeCommon.h"
12
13#include <optional>
14
15#define DEBUG_TYPE "int-range-analysis"
16
17using namespace mlir;
18using namespace mlir::arith;
19using namespace mlir::intrange;
20
21static intrange::OverflowFlags
22convertArithOverflowFlags(arith::IntegerOverflowFlags flags) {
23 intrange::OverflowFlags retFlags = intrange::OverflowFlags::None;
24 if (bitEnumContainsAny(bits: flags, bit: arith::IntegerOverflowFlags::nsw))
25 retFlags |= intrange::OverflowFlags::Nsw;
26 if (bitEnumContainsAny(bits: flags, bit: arith::IntegerOverflowFlags::nuw))
27 retFlags |= intrange::OverflowFlags::Nuw;
28 return retFlags;
29}
30
31//===----------------------------------------------------------------------===//
32// ConstantOp
33//===----------------------------------------------------------------------===//
34
35void arith::ConstantOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
36 SetIntRangeFn setResultRange) {
37 if (auto scalarCstAttr = llvm::dyn_cast_or_null<IntegerAttr>(Val: getValue())) {
38 const APInt &value = scalarCstAttr.getValue();
39 setResultRange(getResult(), ConstantIntRanges::constant(value));
40 return;
41 }
42 if (auto arrayCstAttr =
43 llvm::dyn_cast_or_null<DenseIntElementsAttr>(Val: getValue())) {
44 if (arrayCstAttr.empty())
45 return;
46
47 if (arrayCstAttr.isSplat()) {
48 setResultRange(getResult(), ConstantIntRanges::constant(
49 value: arrayCstAttr.getSplatValue<APInt>()));
50 return;
51 }
52
53 std::optional<ConstantIntRanges> result;
54 for (const APInt &val : arrayCstAttr) {
55 auto range = ConstantIntRanges::constant(value: val);
56 result = (result ? result->rangeUnion(other: range) : range);
57 }
58
59 setResultRange(getResult(), *result);
60 return;
61 }
62
63 auto range = IntegerValueRange::getMaxRange(value: getResult());
64 setResultRange(getResult(), range.getValue());
65}
66
67//===----------------------------------------------------------------------===//
68// AddIOp
69//===----------------------------------------------------------------------===//
70
71void arith::AddIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
72 SetIntRangeFn setResultRange) {
73 setResultRange(getResult(), inferAdd(argRanges, ovfFlags: convertArithOverflowFlags(
74 flags: getOverflowFlags())));
75}
76
77//===----------------------------------------------------------------------===//
78// SubIOp
79//===----------------------------------------------------------------------===//
80
81void arith::SubIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
82 SetIntRangeFn setResultRange) {
83 setResultRange(getResult(), inferSub(argRanges, ovfFlags: convertArithOverflowFlags(
84 flags: getOverflowFlags())));
85}
86
87//===----------------------------------------------------------------------===//
88// MulIOp
89//===----------------------------------------------------------------------===//
90
91void arith::MulIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
92 SetIntRangeFn setResultRange) {
93 setResultRange(getResult(), inferMul(argRanges, ovfFlags: convertArithOverflowFlags(
94 flags: getOverflowFlags())));
95}
96
97//===----------------------------------------------------------------------===//
98// DivUIOp
99//===----------------------------------------------------------------------===//
100
101void arith::DivUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
102 SetIntRangeFn setResultRange) {
103 setResultRange(getResult(), inferDivU(argRanges));
104}
105
106//===----------------------------------------------------------------------===//
107// DivSIOp
108//===----------------------------------------------------------------------===//
109
110void arith::DivSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
111 SetIntRangeFn setResultRange) {
112 setResultRange(getResult(), inferDivS(argRanges));
113}
114
115//===----------------------------------------------------------------------===//
116// CeilDivUIOp
117//===----------------------------------------------------------------------===//
118
119void arith::CeilDivUIOp::inferResultRanges(
120 ArrayRef<ConstantIntRanges> argRanges, SetIntRangeFn setResultRange) {
121 setResultRange(getResult(), inferCeilDivU(argRanges));
122}
123
124//===----------------------------------------------------------------------===//
125// CeilDivSIOp
126//===----------------------------------------------------------------------===//
127
128void arith::CeilDivSIOp::inferResultRanges(
129 ArrayRef<ConstantIntRanges> argRanges, SetIntRangeFn setResultRange) {
130 setResultRange(getResult(), inferCeilDivS(argRanges));
131}
132
133//===----------------------------------------------------------------------===//
134// FloorDivSIOp
135//===----------------------------------------------------------------------===//
136
137void arith::FloorDivSIOp::inferResultRanges(
138 ArrayRef<ConstantIntRanges> argRanges, SetIntRangeFn setResultRange) {
139 return setResultRange(getResult(), inferFloorDivS(argRanges));
140}
141
142//===----------------------------------------------------------------------===//
143// RemUIOp
144//===----------------------------------------------------------------------===//
145
146void arith::RemUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
147 SetIntRangeFn setResultRange) {
148 setResultRange(getResult(), inferRemU(argRanges));
149}
150
151//===----------------------------------------------------------------------===//
152// RemSIOp
153//===----------------------------------------------------------------------===//
154
155void arith::RemSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
156 SetIntRangeFn setResultRange) {
157 setResultRange(getResult(), inferRemS(argRanges));
158}
159
160//===----------------------------------------------------------------------===//
161// AndIOp
162//===----------------------------------------------------------------------===//
163
164void arith::AndIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
165 SetIntRangeFn setResultRange) {
166 setResultRange(getResult(), inferAnd(argRanges));
167}
168
169//===----------------------------------------------------------------------===//
170// OrIOp
171//===----------------------------------------------------------------------===//
172
173void arith::OrIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
174 SetIntRangeFn setResultRange) {
175 setResultRange(getResult(), inferOr(argRanges));
176}
177
178//===----------------------------------------------------------------------===//
179// XOrIOp
180//===----------------------------------------------------------------------===//
181
182void arith::XOrIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
183 SetIntRangeFn setResultRange) {
184 setResultRange(getResult(), inferXor(argRanges));
185}
186
187//===----------------------------------------------------------------------===//
188// MaxSIOp
189//===----------------------------------------------------------------------===//
190
191void arith::MaxSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
192 SetIntRangeFn setResultRange) {
193 setResultRange(getResult(), inferMaxS(argRanges));
194}
195
196//===----------------------------------------------------------------------===//
197// MaxUIOp
198//===----------------------------------------------------------------------===//
199
200void arith::MaxUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
201 SetIntRangeFn setResultRange) {
202 setResultRange(getResult(), inferMaxU(argRanges));
203}
204
205//===----------------------------------------------------------------------===//
206// MinSIOp
207//===----------------------------------------------------------------------===//
208
209void arith::MinSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
210 SetIntRangeFn setResultRange) {
211 setResultRange(getResult(), inferMinS(argRanges));
212}
213
214//===----------------------------------------------------------------------===//
215// MinUIOp
216//===----------------------------------------------------------------------===//
217
218void arith::MinUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
219 SetIntRangeFn setResultRange) {
220 setResultRange(getResult(), inferMinU(argRanges));
221}
222
223//===----------------------------------------------------------------------===//
224// ExtUIOp
225//===----------------------------------------------------------------------===//
226
227void arith::ExtUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
228 SetIntRangeFn setResultRange) {
229 unsigned destWidth =
230 ConstantIntRanges::getStorageBitwidth(type: getResult().getType());
231 setResultRange(getResult(), extUIRange(range: argRanges[0], destWidth));
232}
233
234//===----------------------------------------------------------------------===//
235// ExtSIOp
236//===----------------------------------------------------------------------===//
237
238void arith::ExtSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
239 SetIntRangeFn setResultRange) {
240 unsigned destWidth =
241 ConstantIntRanges::getStorageBitwidth(type: getResult().getType());
242 setResultRange(getResult(), extSIRange(range: argRanges[0], destWidth));
243}
244
245//===----------------------------------------------------------------------===//
246// TruncIOp
247//===----------------------------------------------------------------------===//
248
249void arith::TruncIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
250 SetIntRangeFn setResultRange) {
251 unsigned destWidth =
252 ConstantIntRanges::getStorageBitwidth(type: getResult().getType());
253 setResultRange(getResult(), truncRange(range: argRanges[0], destWidth));
254}
255
256//===----------------------------------------------------------------------===//
257// IndexCastOp
258//===----------------------------------------------------------------------===//
259
260void arith::IndexCastOp::inferResultRanges(
261 ArrayRef<ConstantIntRanges> argRanges, SetIntRangeFn setResultRange) {
262 Type sourceType = getOperand().getType();
263 Type destType = getResult().getType();
264 unsigned srcWidth = ConstantIntRanges::getStorageBitwidth(type: sourceType);
265 unsigned destWidth = ConstantIntRanges::getStorageBitwidth(type: destType);
266
267 if (srcWidth < destWidth)
268 setResultRange(getResult(), extSIRange(range: argRanges[0], destWidth));
269 else if (srcWidth > destWidth)
270 setResultRange(getResult(), truncRange(range: argRanges[0], destWidth));
271 else
272 setResultRange(getResult(), argRanges[0]);
273}
274
275//===----------------------------------------------------------------------===//
276// IndexCastUIOp
277//===----------------------------------------------------------------------===//
278
279void arith::IndexCastUIOp::inferResultRanges(
280 ArrayRef<ConstantIntRanges> argRanges, SetIntRangeFn setResultRange) {
281 Type sourceType = getOperand().getType();
282 Type destType = getResult().getType();
283 unsigned srcWidth = ConstantIntRanges::getStorageBitwidth(type: sourceType);
284 unsigned destWidth = ConstantIntRanges::getStorageBitwidth(type: destType);
285
286 if (srcWidth < destWidth)
287 setResultRange(getResult(), extUIRange(range: argRanges[0], destWidth));
288 else if (srcWidth > destWidth)
289 setResultRange(getResult(), truncRange(range: argRanges[0], destWidth));
290 else
291 setResultRange(getResult(), argRanges[0]);
292}
293
294//===----------------------------------------------------------------------===//
295// CmpIOp
296//===----------------------------------------------------------------------===//
297
298void arith::CmpIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
299 SetIntRangeFn setResultRange) {
300 arith::CmpIPredicate arithPred = getPredicate();
301 intrange::CmpPredicate pred = static_cast<intrange::CmpPredicate>(arithPred);
302 const ConstantIntRanges &lhs = argRanges[0], &rhs = argRanges[1];
303
304 APInt min = APInt::getZero(numBits: 1);
305 APInt max = APInt::getAllOnes(numBits: 1);
306
307 std::optional<bool> truthValue = intrange::evaluatePred(pred, lhs, rhs);
308 if (truthValue.has_value() && *truthValue)
309 min = max;
310 else if (truthValue.has_value() && !(*truthValue))
311 max = min;
312
313 setResultRange(getResult(), ConstantIntRanges::fromUnsigned(umin: min, umax: max));
314}
315
316//===----------------------------------------------------------------------===//
317// SelectOp
318//===----------------------------------------------------------------------===//
319
320void arith::SelectOp::inferResultRangesFromOptional(
321 ArrayRef<IntegerValueRange> argRanges, SetIntLatticeFn setResultRange) {
322 std::optional<APInt> mbCondVal =
323 argRanges[0].isUninitialized()
324 ? std::nullopt
325 : argRanges[0].getValue().getConstantValue();
326
327 const IntegerValueRange &trueCase = argRanges[1];
328 const IntegerValueRange &falseCase = argRanges[2];
329
330 if (mbCondVal) {
331 if (mbCondVal->isZero())
332 setResultRange(getResult(), falseCase);
333 else
334 setResultRange(getResult(), trueCase);
335 return;
336 }
337
338 // When one of the ranges is uninitialized, set the whole range to max
339 // otherwise the result will ignore the uninitialized range.
340 if (trueCase.isUninitialized() || falseCase.isUninitialized())
341 setResultRange(getResult(), IntegerValueRange::getMaxRange(value: getResult()));
342 else
343 setResultRange(getResult(), IntegerValueRange::join(lhs: trueCase, rhs: falseCase));
344}
345
346//===----------------------------------------------------------------------===//
347// ShLIOp
348//===----------------------------------------------------------------------===//
349
350void arith::ShLIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
351 SetIntRangeFn setResultRange) {
352 setResultRange(getResult(), inferShl(argRanges, ovfFlags: convertArithOverflowFlags(
353 flags: getOverflowFlags())));
354}
355
356//===----------------------------------------------------------------------===//
357// ShRUIOp
358//===----------------------------------------------------------------------===//
359
360void arith::ShRUIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
361 SetIntRangeFn setResultRange) {
362 setResultRange(getResult(), inferShrU(argRanges));
363}
364
365//===----------------------------------------------------------------------===//
366// ShRSIOp
367//===----------------------------------------------------------------------===//
368
369void arith::ShRSIOp::inferResultRanges(ArrayRef<ConstantIntRanges> argRanges,
370 SetIntRangeFn setResultRange) {
371 setResultRange(getResult(), inferShrS(argRanges));
372}
373