[mlir][affine] Loop transformations can miscompile when dependence analysis fails
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
Affine loop tiling and validity-checked loop permutation can proceed when
`checkMemrefAccessDependence` returns `DependenceResult::Failure`.
`Failure` means that dependence analysis could not construct the access
relation; it does not prove that the accesses are independent. Proceeding with
the transformation can therefore reverse a real loop-carried dependence.
I reproduced this on `llvm-project` commit `446a84a7c66e`.
## Reproducer
```mlir
#dynamic_index = affine_map<()[s0, s1] -> (s0 * s1)>
func.func @unknown_dependence(
%A: memref, %B: memref<9x9xi32>,
%p: index, %q: index, %value: i32) {
affine.for %i = 1 to 8 {
affine.for %j = 1 to 8 {
%z = affine.apply #dynamic_index()[%p, %q]
affine.store %value, %A[%z, %i, %j] : memref
%loaded = affine.load %A[%z, %i - 1, %j + 1]
: memref
affine.store %loaded, %B[%i, %j] : memref<9x9xi32>
}
}
return
}
```
With an MLIR build that includes the test passes:
```shell
mlir-opt reproducer.mlir \
-test-loop-permutation='permutation-map=1,0 check-validity=1'
mlir-opt reproducer.mlir -affine-loop-tile='tile-size=4'
```
## Expected behavior
Both transformations should leave the original loop nest unchanged because
dependence analysis could not prove that the requested schedule is legal.
## Actual behavior
The first command interchanges the two loops. The second command generates a
tiled four-loop nest.
The common first subscript `%z` is identical for both accesses. In the
remaining two dimensions, the store-to-load dependence has distance
`(1, -1)`. The original loop order preserves this dependence, but the
generated schedules can reverse it.
## Related issue
This is related to #191147, but it is a different failure mode. In #191147,
dependence analysis succeeds and produces a component with
`lb == ub == -1`; the subsequent component-bound check in `isTilingValid`
misses that exact negative distance.
In this reproducer, access-relation construction itself returns `Failure`.
That unknown result is then treated like `NoDependence`, before any dependence
components are inspected. The proposed fix in #192858 changes only the
component-bound check, so it does not handle this case. This issue also affects
the `getDependenceComponents` users, not only loop tiling.
## Cause
Two callers lose the distinction between `NoDependence` and `Failure`:
- `isTilingValid` skips a pair when `!hasDependence(result)`, which is true for
both `NoDependence` and `Failure`.
- `getDependenceComponents` returns `void` and appends only successfully
computed dependence components. Loop-permutation validation and
`sinkSequentialLoops` can therefore consume a partial dependence graph as
though it were complete.
Assisted-by: OpenAI Codex
Contributor guide
Assessment
This issue has not been assessed yet.