[mlir] Fix wrong names in LinalgOps and ScalableValueBoundsConstraintSet (#117227)

Fix for some mistakes in source code found using PVS Studio.

Inspired by: https://pvs-studio.com/en/blog/posts/cpp

[mlir] Fix wrong names in LinalgOps and ScalableValueBoundsConstraintSet (#117227)

Fix for some mistakes in source code found using PVS Studio.

Inspired by: https://pvs-studio.com/en/blog/posts/cpp/1188/

Fixed:
- [Bug 2](https://pvs-studio.com/en/blog/posts/cpp/1188/#ID725051E718)
- [Bug 3](https://pvs-studio.com/en/blog/posts/cpp/1188/#IDFA2459368E)

show more ...

[mlir][vector] Project out anonymous bounds in ScalableValueBoundsConstraintSet (#96499)

If we don't eliminate these columns, then in some cases we fail to
compute a scalable bound. Test case reduc

[mlir][vector] Project out anonymous bounds in ScalableValueBoundsConstraintSet (#96499)

If we don't eliminate these columns, then in some cases we fail to
compute a scalable bound. Test case reduced from a real-world example.

show more ...

[mlir][affine][Analysis] Add conservative bounds for semi-affine mods (#93576)

This patch adds support for computing bounds for semi-affine mod
expression to FlatLinearConstraints. This is then ena

[mlir][affine][Analysis] Add conservative bounds for semi-affine mods (#93576)

This patch adds support for computing bounds for semi-affine mod
expression to FlatLinearConstraints. This is then enabled within the
ScalableValueBoundsConstraintSet to allow computing the bounds of
scalable remainder loops.

E.g. computing the bound of something like:
```
// `1000 mod s0` is a semi-affine.
#remainder_start_index = affine_map<()[s0] -> (-(1000 mod s0) + 1000)>
#remaining_iterations = affine_map<(d0) -> (-d0 + 1000)>

%0 = affine.apply #remainder_start_index()[%c8_vscale]
scf.for %i = %0 to %c1000 step %c8_vscale {
%remaining_iterations = affine.apply #remaining_iterations(%i)
// The upper bound for the remainder loop iterations should be:
// %c8_vscale - 1 (expressed as an affine map,
// affine_map<()[s0] -> (s0 * 8 - 1)>, where s0 is vscale)
%bound = "test.reify_bound"(%remaining_iterations) <{scalable, ...}>
}
```

There are caveats to this implementation. To be able to add a bound for
a `mod` we need to assume the rhs is positive (> 0). This may not be
known when adding the bounds for the `mod` expression. So to handle this
a constraint is added for `rhs > 0`, this may later be found not to hold
(in which case the constraints set becomes empty/invalid).

This is not a problem for computing scalable bounds where it's safe to
assume `s0` is vscale (or some positive multiple of it). But this may
need to be considered when enabling this feature elsewhere (to ensure
correctness).

show more ...

[mlir][SCF] `ValueBoundsConstraintSet`: Support `scf.if` (branches) (#87860)

This commit adds support for `scf.if` to `ValueBoundsConstraintSet`.

Example:
```
%0 = scf.if ... -> index {
scf.

[mlir][SCF] `ValueBoundsConstraintSet`: Support `scf.if` (branches) (#87860)

This commit adds support for `scf.if` to `ValueBoundsConstraintSet`.

Example:
```
%0 = scf.if ... -> index {
scf.yield %a : index
} else {
scf.yield %b : index
}
```

The following constraints hold for %0:
* %0 >= min(%a, %b)
* %0 <= max(%a, %b)

Such constraints cannot be added to the constraint set; min/max is not
supported by `IntegerRelation`. However, if we know which one of %a and
%b is larger, we can add constraints for %0. E.g., if %a <= %b:
* %0 >= %a
* %0 <= %b

This commit required a few minor changes to the
`ValueBoundsConstraintSet` infrastructure, so that values can be
compared while we are still in the process of traversing the IR/adding
constraints.

Note: This is a re-upload of #85895, which was reverted. The bug that
caused the failure was fixed in #87859.

show more ...

Revert "[mlir][SCF] `ValueBoundsConstraintSet`: Support `scf.if` (branches) (#85895)"

This reverts commit 6b30ffef28c35c24bfd8190e06eeaa0c5cd73cbd.

gcc7 bot is broken

[mlir][SCF] `ValueBoundsConstraintSet`: Support `scf.if` (branches) (#85895)

This commit adds support for `scf.if` to `ValueBoundsConstraintSet`.

Example:
```
%0 = scf.if ... -> index {
scf.

[mlir][SCF] `ValueBoundsConstraintSet`: Support `scf.if` (branches) (#85895)

This commit adds support for `scf.if` to `ValueBoundsConstraintSet`.

Example:
```
%0 = scf.if ... -> index {
scf.yield %a : index
} else {
scf.yield %b : index
}
```

The following constraints hold for %0:
* %0 >= min(%a, %b)
* %0 <= max(%a, %b)

Such constraints cannot be added to the constraint set; min/max is not
supported by `IntegerRelation`. However, if we know which one of %a and
%b is larger, we can add constraints for %0. E.g., if %a <= %b:
* %0 >= %a
* %0 <= %b

This commit required a few minor changes to the
`ValueBoundsConstraintSet` infrastructure, so that values can be
compared while we are still in the process of traversing the IR/adding
constraints.

show more ...

[mlir][Interfaces][NFC] `ValueBoundsConstraintSet`: Pass stop condition in the constructor (#86099)

This commit changes the API of `ValueBoundsConstraintSet`: the stop
condition is now passed to th

[mlir][Interfaces][NFC] `ValueBoundsConstraintSet`: Pass stop condition in the constructor (#86099)

This commit changes the API of `ValueBoundsConstraintSet`: the stop
condition is now passed to the constructor instead of `processWorklist`.
That makes it easier to add items to the worklist multiple times and
process them in a consistent manner. The current
`ValueBoundsConstraintSet` is passed as a reference to the stop
function, so that the stop function can be defined before the the
`ValueBoundsConstraintSet` is constructed.

This change is in preparation of adding support for branches.

show more ...

[mlir][Vector] Add utility for computing scalable value bounds (#83876)

This adds a new API built with the `ValueBoundsConstraintSet` to compute
the bounds of possibly scalable quantities. It uses

[mlir][Vector] Add utility for computing scalable value bounds (#83876)

This adds a new API built with the `ValueBoundsConstraintSet` to compute
the bounds of possibly scalable quantities. It uses knowledge of the
range of vscale (which is defined by the target architecture), to solve
for the bound as either a constant or an expression in terms of vscale.

The result is an `AffineMap` that will always take at most one
parameter, vscale, and returns a single result, which is the bound of
`value`.

The API is defined as follows:

```c++
FailureOr<ConstantOrScalableBound>
vector::ScalableValueBoundsConstraintSet::computeScalableBound(
Value value, std::optional<int64_t> dim,
unsigned vscaleMin, unsigned vscaleMax,
presburger::BoundType boundType,
bool closedUB = true,
StopConditionFn stopCondition = nullptr);
```

Note: `ConstantOrScalableBound` is a thin wrapper over the `AffineMap`
with a utility for converting the bound to a single quantity (i.e. a
size and scalable flag).

We believe this API could prove useful downstream in IREE (which uses a
similar analysis to hoist allocas, which currently fails for scalable
vectors).

show more ...