[mlir][IntRangeInference] Fix `arith.ceildivsi` range inference when it includes `INT_MIN` (#121062)

There is a special case in `arith.ceildivsi` range inference for
handling `lhs.smin()==INT_MIN`,

[mlir][IntRangeInference] Fix `arith.ceildivsi` range inference when it includes `INT_MIN` (#121062)

There is a special case in `arith.ceildivsi` range inference for
handling `lhs.smin()==INT_MIN`, but when `lhs` is not a single value, it
can cause it to skip entire negative range. Add `lhs.smin() + 1` check
to handle it.

show more ...

[mlir][int-range] Update int range inference for `arith.xori` (#117272)

Previous impl was getting incorrect results for widths > i1 and was
disabled.

While same algorithm can be used for `andi`

[mlir][int-range] Update int range inference for `arith.xori` (#117272)

Previous impl was getting incorrect results for widths > i1 and was
disabled.

While same algorithm can be used for `andi` and `ori` too, without
additional modifications it will produce less precise result.

show more ...

[mlir][int-range] Limit xor int range inference to i1 (#116968)

Fixes https://github.com/llvm/llvm-project/issues/82168

`intrange::inferXor` was incorrectly handling ranges for widths > i1
(see

[mlir][int-range] Limit xor int range inference to i1 (#116968)

Fixes https://github.com/llvm/llvm-project/issues/82168

`intrange::inferXor` was incorrectly handling ranges for widths > i1
(see example in code). Limit it to i1 for now. For bigger widths it will
return maxRange.

show more ...

[mlir][IntRangeInference] Handle ceildivsi(INT_MIN, x > 1) as expected (#116284)

Fixes #115293

While the definition of ceildivsi is integer division, rounding up, most
implementations will use `

[mlir][IntRangeInference] Handle ceildivsi(INT_MIN, x > 1) as expected (#116284)

Fixes #115293

While the definition of ceildivsi is integer division, rounding up, most
implementations will use `-(-a / b)` for dividing `a ceildiv b` with `a`
negative and `b` positive.

Mathematically, and for most integers, these two definitions are
equivalent. However, with `a == INT_MIN`, the initial negation is a
noop, which means that, while divinding and rounding up would give a
negative result, `-((- INT_MIN) / b)` is `-(INT_MIN / b)`, which is
positive.

This commit adds a special case to ceilDivSI inference to handle this
case and bring it in line with the operational instead of the
mathematical semantics of ceiling division.

show more ...

[MLIR] Fix dangling llvm::function_ref references (#114950)

[MLIR][Arith] Improve accuracy of `inferDivU` (#113789)

1) We can always bound the maximum with the numerator.
- https://alive2.llvm.org/ce/z/PqHvuT
2) Even if denominator min can be zero, we

[MLIR][Arith] Improve accuracy of `inferDivU` (#113789)

1) We can always bound the maximum with the numerator.
- https://alive2.llvm.org/ce/z/PqHvuT
2) Even if denominator min can be zero, we can still bound the minimum
result with `lhs.umin u/ rhs.umax`.

This is similar to https://github.com/llvm/llvm-project/pull/110169

show more ...

[MLIR] Unconditionally take min of max lhs/rhs value in inferRemU (#110169)

- **[MLIR] Add test for inferring range of remu; NFC**
- **[MLIR] Unconditionally take min of max lhs/rhs value in inferR

[MLIR] Unconditionally take min of max lhs/rhs value in inferRemU (#110169)

- **[MLIR] Add test for inferring range of remu; NFC**
- **[MLIR] Unconditionally take min of max lhs/rhs value in inferRemU**

`arith.remu` cannot be larger than (rhs - 1) or lhs.

show more ...

Fix Android build failure in InferIntRangeCommon (#96154)

As of today, Android's libcxx is missing C++17's std::function's CTAD
added in e1eabcdfad89f67ae575b0c86aa4a72d277378b4. This leads to
Inf

Fix Android build failure in InferIntRangeCommon (#96154)

As of today, Android's libcxx is missing C++17's std::function's CTAD
added in e1eabcdfad89f67ae575b0c86aa4a72d277378b4. This leads to
InferIntRangeCommon.cpp to fail to compile. This commit makes the
template parameter of std::function in that function explicit, therefore
avoiding CTAD. While LLVM/MLIR's requirement is C++17, the rest of the
code builds fine so hopefully this is acceptable.

show more ...

[mlir][dataflow] Fix for integer range analysis propagation bug (#93199)

Integer range analysis will not update the range of an operation when
any of the inferred input lattices are uninitialized.

[mlir][dataflow] Fix for integer range analysis propagation bug (#93199)

Integer range analysis will not update the range of an operation when
any of the inferred input lattices are uninitialized. In the current
behavior, all lattice values for non integer types are uninitialized.

For operations like arith.cmpf

```mlir
%3 = arith.cmpf ugt, %arg0, %arg1 : f32
```

that will result in the range of the output also being uninitialized,
and so on for any consumer of the arith.cmpf result. When control-flow
ops are involved, the lack of propagation results in incorrect ranges,
as the back edges for loop carried values are not properly joined with
the definitions from the body region.

For example, an scf.while loop whose body region produces a value that
is in a dataflow relationship with some floating-point values through an
arith.cmpf operation:

```mlir
func.func @test_bad_range(%arg0: f32, %arg1: f32) -> (index, index) {
%c4 = arith.constant 4 : index
%c1 = arith.constant 1 : index
%c0 = arith.constant 0 : index

%3 = arith.cmpf ugt, %arg0, %arg1 : f32

%1:2 = scf.while (%arg2 = %c0, %arg3 = %c0) : (index, index) -> (index, index) {
%2 = arith.cmpi ult, %arg2, %c4 : index
scf.condition(%2) %arg2, %arg3 : index, index
} do {
^bb0(%arg2: index, %arg3: index):
%4 = arith.select %3, %arg3, %arg3 : index
%5 = arith.addi %arg2, %c1 : index
scf.yield %5, %4 : index, index
}

return %1#0, %1#1 : index, index
}
```

The existing behavior results in the control condition %2 being
optimized to true, turning the while loop into an infinite loop. The
update to %arg2 through the body region is never factored into the range
calculation, as the ranges for the body ops all test as uninitialized.

This change causes all values initialized with setToEntryState to be set
to some initialized range, even if the values are not integers.

---------

Co-authored-by: Spenser Bauman <sabauma@fastmail>

show more ...

[mlir][intrange] Use `nsw`,`nuw` flags in inference (#92642)

This patch includes the "no signed wrap" and "no unsigned wrap" flags,
which can be used to annotate some Ops in the `arith` dialect and

[mlir][intrange] Use `nsw`,`nuw` flags in inference (#92642)

This patch includes the "no signed wrap" and "no unsigned wrap" flags,
which can be used to annotate some Ops in the `arith` dialect and also
in LLVMIR, in the integer range inference.

The general approach is to use saturating arithmetic operations to infer
bounds which are assumed to not wrap and use overflowing arithmetic
operations in the normal case. If overflow is detected in the normal
case,
special handling makes sure that we don't underestimate the result
range.

show more ...

[mlir][intrange] Fix `arith.shl` inference in case of overflow (#91737)

When an overflow happens during shift left, i.e. the last sign bit or
the most significant data bit gets shifted out, the cur

[mlir][intrange] Fix `arith.shl` inference in case of overflow (#91737)

When an overflow happens during shift left, i.e. the last sign bit or
the most significant data bit gets shifted out, the current approach of
inferring the range of results does not work anymore.

This patch checks for possible overflow and returns the max range in
that case.

Fix https://github.com/llvm/llvm-project/issues/82158

show more ...

Use APInt::count{l,r}_{zero,one} (NFC)

[mlir][Index] Implement InferIntRangeInterface, re-land

Re-land D140899 to fix a missing dependency in the index dialect's
CMakeLists.txt.

Reviewed By: Mogball

Differential Revision: https://revie

[mlir][Index] Implement InferIntRangeInterface, re-land

Re-land D140899 to fix a missing dependency in the index dialect's
CMakeLists.txt.

Reviewed By: Mogball

Differential Revision: https://reviews.llvm.org/D142147

show more ...

[mlir][Index] Implement InferIntRangeInterface

Implement InferIntRangeInterface for all operations in the Index dialect. The
inference implementation, unlike the one for Arith, accounts for the
fact

[mlir][Index] Implement InferIntRangeInterface

Implement InferIntRangeInterface for all operations in the Index dialect. The
inference implementation, unlike the one for Arith, accounts for the
fact that Index can be either 64 or 32 bits long by evaluating both
cases. Bounds are stored as if index were i64, but when inferring new
bounds, we compute both f(...) and f(trunc(...)). We then compare
trunc(f(...)) to f(trunc(...)). If they are equal in the relevant
range components, we use the 64-bit range computation, otherwise we
give the range ext(f(trunc(...))) union f(...).

Note that this can cause surprising behavior as seen in the tests,
where, for example, the order of min and max operations impacts the
behavior of the inference. The inference could perhaps be made more
precise in the future (ex. by tracking 32 and 64-bit results
separately and having them influence each other somehow) butt, since
my project targets an index=i32 platform and doesn't see index-valued
values > uint32_max, I'm not too concerned about it.

Depends on https://reviews.llvm.org/D141299

Depends on https://reviews.llvm.org/D141296

Reviewed By: Mogball

Differential Revision: https://reviews.llvm.org/D140899

show more ...