llvm / llvm/llvm-project

[MLIR][Affine] affine-loop-fusion omits recurrence predecessors when slicing a producer

Open
#212,041 1 comment 0 reactions 0 assignees View on GitHub
mlir
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.