llvm / llvm/llvm-project

[mlir][affine] Loop transformations can miscompile when dependence analysis fails

Open
#210,585 7 comments 0 reactions 1 assignee Claimed by @purnima-nlp View on GitHub
miscompilation mlir:affine
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.