| Issue |
244186
|
| Summary |
[mlir][Presburger] getConstantBound ignores that r = c*q is a multiple of c: upper bound of (x floordiv 16) * 16 is loose
|
| Labels |
mlir
|
| Assignees |
|
| Reporter |
Devjiu
|
Hi,
Looks like `getConstantBound` works incorrectly for aligned shapes.
`IntegerRelation::getConstantBound` (reached via `ValueBoundsConstraintSet::computeConstantBound`) returns a loose upper bound for a variable that is defined as `r = c * q` where `q` is a floordiv local. The bound for `q` itself is tight, but the bound for `r` is not `c * UB(q)`: the divisibility of `r` by `c` is lost.
So, roughly speaking, if we have `(x floordiv 16) * 16` and are looking for UpperBound/max of this _expression_, we are discarding 16 and looking just `max(x)`. This leads us to an inaccurate upper bound, which also misses the required alignment.
### Illustrations:
`x` is in [0, 10], so `(x floordiv 4) * 4` can be at most 8.
```mlir
func.func @round_down(%a: index) -> index {
%x = affine.min affine_map<(d0) -> (d0, 10)>(%a)
%r = affine.apply affine_map<(d0) -> ((d0 floordiv 4) * 4)>(%x)
%ub = "test.reify_bound"(%r) {type = "UB", constant} : (index) -> index
return %ub : index
}
```
```
mlir-opt repro.mlir -pass-pipeline='builtin.module(func.func(test-affine-reify-value-bounds))'
```
Solver says `r` can be as large as
Actual: 10 (the test pass prints the exclusive bound, `arith.constant 11`).
Expected: 8 (`arith.constant 9` in the test pass's exclusive form). 10 is impossible: `r` is a multiple of 4, nd the largest multiple of 4 that does not exceed `x <= 10` is 8.
AI helped me to reduce it to Presburger:
Variables `[r, x, q]`, with `r = 4*q`, `4*q <= x <= 4*q + 3` (i.e. `q = floordiv(x, 4)`) and `0 <= x <= 10`:
```cpp
IntegerPolyhedron p(PresburgerSpace::getSetSpace(3));
p.addEquality({1, 0, -4, 0}); // r - 4q = 0
p.addInequality({0, 1, -4, 0}); // x - 4q >= 0
p.addInequality({0, -1, 4, 3}); // 4q + 3 - x >= 0
p.addInequality({0, 1, 0, 0}); // x >= 0
p.addInequality({0, -1, 0, 10}); // 10 - x >= 0
p.getConstantBound64(BoundType::UB, /*r=*/0); // 10, expected 8
p.getConstantBound64(BoundType::UB, /*q=*/2); // 2 -> 4 * 2 = 8
```
`UB(q) = 2`, but `UB(r) = 10` although `r = 4q`. The result depends on how `r = 4q` is written:
| variant | UB(r) |
|---|---|
| equality `r - 4q = 0`, order `[r, x, q]` | 10 |
| equality `r - 4q = 0`, order `[q, x, r]` | 10 |
| two inequalities (`r - 4q >= 0` and `4q - r >= 0`) | **8** |
Eliminating `q` through `r = 4q` seems expected. But when the upper bound of `r` is returned, the alignment that was dropped during the elimination should be taken into account. `r` is a multiple of 4, so the bound 10 can be rounded down to 8, which equals `4 * UB(q)`.
More generally, the dropped information is "`r` is a multiple of `gcd` of the coefficients of the variables eliminated through this equality", so keeping that gcd next to the equality (or applying the rounding right after the elimination) would be enough to recover the tight bound in this case.
### Question
Is this a known limitation of equality elimination with non-unit pivot coefficients? Possible directions: skip Gaussian pivoting on equalities with `|coeff| > 1` when computing bounds, or keep the divisibility information after elimination.
I've done a local WA using `getLargestKnownDivisor()`, but it also seems it should be taken into account during analysis.
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs