[MLIR][Affine] affine-loop-fusion omits recurrence predecessors when slicing a producer
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Summary
Applying producer/maximal `affine-loop-fusion` to the verifier-valid program below generates a verifier-valid target containing in-bounds loads from local buffer elements that have no reaching store.
The producer computes the recurrence:
```text
tmp[0] = 29
tmp[i] = tmp[i - 1] + in[i], 1 <= i < 16
```
The consumer directly reads only the even points `tmp[2 * j]`. Fusion selects and clones those directly demanded producer iterations, but does not include the odd recurrence predecessors required to compute them.
The original complete producer loop is removed, leaving loads from `tmp[1]`, `tmp[3]`, ..., `tmp[13]` without any corresponding store.
Public `mlir-opt` reproducer:
https://godbolt.org/z/hsPne4EEY
## Version
Tested at `llvm/llvm-project` commit: `450cf0aafeab9fed6666b112b018d3913a36527c`
LLVM version:
```text
LLVM 24.0.0git
```
Release builds with assertions enabled and disabled generated the same transformed IR.
## Reproducer
```mlir
module {
func.func @neutral(
%in: memref<32xf64>,
%out: memref<32xf64>) {
%tmp = memref.alloc() : memref<32xf64>
%seed_value = arith.constant 2.900000e+01 : f64
affine.store %seed_value, %tmp[0] : memref<32xf64>
affine.for %i = 1 to 16 {
%prev = affine.load %tmp[%i - 1] : memref<32xf64>
%src_load = affine.load %in[%i] : memref<32xf64>
%src_v0 = arith.addf %prev, %src_load : f64
affine.store %src_v0, %tmp[%i] : memref<32xf64>
}
affine.for %j = 1 to 8 {
%dst_load = affine.load %tmp[2 * %j] : memref<32xf64>
%dst_v0 = arith.addf %dst_load, %dst_load : f64
affine.store %dst_v0, %out[%j] : memref<32xf64>
}
return
}
}
```
## Commands
```sh
# Baseline.
mlir-opt input.mlir \
-o baseline.mlir
# Apply producer/maximal affine loop fusion to the same input.
mlir-opt input.mlir \
--pass-pipeline='builtin.module(func.func(affine-loop-fusion{mode=producer maximal}))' \
-o fused.mlir
# The generated target also passes MLIR verification.
mlir-opt fused.mlir \
-o /dev/null
```
## Actual behavior
The generated function is:
```mlir
#map = affine_map<(d0) -> (d0 * 2)>
module {
func.func @neutral(
%arg0: memref<32xf64>,
%arg1: memref<32xf64>) {
%alloc = memref.alloc() : memref<32xf64>
%cst = arith.constant 2.900000e+01 : f64
affine.store %cst, %alloc[0] : memref<32xf64>
affine.for %arg2 = 1 to 8 {
%0 = affine.apply #map(%arg2)
%1 = affine.load %alloc[%0 - 1] : memref<32xf64>
%2 = affine.load %arg0[%0] : memref<32xf64>
%3 = arith.addf %1, %2 : f64
affine.store %3, %alloc[%0] : memref<32xf64>
%4 = affine.load %alloc[%arg2 * 2] : memref<32xf64>
%5 = arith.addf %4, %4 : f64
affine.store %5, %arg1[%arg2] : memref<32xf64>
}
return
}
}
```
For `%arg2 = 1..7`, `%0 = 2 * %arg2`.
The generated stores to `%alloc` therefore target:
```text
0, 2, 4, 6, 8, 10, 12, 14
```
The cloned producer predecessor load:
```mlir
%1 = affine.load %alloc[%0 - 1] : memref<32xf64>
```
instead accesses:
```text
1, 3, 5, 7, 9, 11, 13
```
No operation in the generated target stores any of these odd indices. Consequently, every one of these loads is in bounds but has no dominating or loop-carried reaching store.
In the source program, the recurrence is evaluated sequentially:
```text
tmp[0] -> tmp[1] -> tmp[2] -> ... -> tmp[15]
```
Computing a directly demanded even point such as `tmp[2]` requires `tmp[1]`; computing `tmp[4]` requires `tmp[3]`, and so on. The complete producer set required for consumer points `{2, 4, 6, 8, 10, 12, 14}` is therefore:
```text
{0, 1, 2, ..., 14}
```
The generated target materializes only:
```text
{0, 2, 4, 6, 8, 10, 12, 14}
```
This is a static property of the transformed IR. Because the generated target contains loads without reaching definitions, no target runtime value is used as the semantic oracle for this report.
## Expected behavior
When slicing a producer that contains a recurrence, `affine-loop-fusion` should include every recurrence predecessor required to compute the directly demanded producer points.
For this program, the selected producer set must be closed over:
```text
Pred(i) = i - 1
```
Alternatively, the pass should retain the original producer computation or decline the fusion.
The pass must not remove the complete producer loop while leaving cloned producer loads whose source values are never defined.
## Validity
The source recurrence is fully defined:
- `%tmp[0]` is initialized before the producer loop;
- at producer iteration `i`, `%tmp[i - 1]` has already been stored by the seed or the preceding iteration;
- the producer stores `%tmp[i]` before any later iteration reads it.
All source accesses are within `memref<32xf64>`:
- `%tmp[i - 1]` uses indices 0 through 14;
- `%tmp[i]` and `%in[i]` use indices 1 through 15;
- `%tmp[2 * j]` uses indices 2 through 14;
- `%out[j]` uses indices 1 through 7.
All generated target accesses are also in bounds. The failure is not an out-of-bounds access: it is the absence of reaching stores for the generated loads from odd recurrence-predecessor indices.
Both the source and generated target pass MLIR verification. The missing memory definitions are introduced only by `affine-loop-fusion`.
Contributor guide
Research direction
Start with the input.mlir reproducer and run mlir-opt with and without the affine-loop-fusion{mode=producer maximal} pipeline. Trace the affine-loop-fusion producer slicing and its handling of the recurrence predecessor load. Done means the fused result includes all required predecessors, retains the producer, or declines fusion without creating loads lacking reaching stores.
Written by the indexing model from the issue text.
Assessment
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Clearly specified
- Newbie friendliness
- 52/100