[MLIR][Affine] Miscompilation: `affine-loop-fusion` misses the dependence between two memref.get_global handles to the same buffer
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
`memref.get_global @g` twice gives two SSA values denoting the *same* buffer. The affine dependence graph is keyed on the SSA value, so accesses through one handle are invisible to accesses through the other. Fusion then moves a write to the buffer past an intervening read, causing the read to observe the original contents instead of the updated contents.
The program below does four things to one global: multiply every element by 11, reduce the buffer into an accumulator, add 7 to every element, reduce again. The second step reads through a *second* `memref.get_global @g` and nothing else about it is unusual.
Starting from `dense<[1, 2, 3, 4]>` and `%init = 0`: step 1 leaves `[11, 22, 33, 44]`, so step 2 subtracts 110; step 3 leaves `[18, 29, 40, 51]`, so step 4 subtracts 138. The answer is `-248`. With `--affine-loop-fusion` it prints `-148`, which is `0 - 10 - 138`: the second step subtracted `1+2+3+4 = 10`, the *original* contents. Fusion merged step 1 into step 3 — both write the buffer through `%a` — which moves the multiplication to after the reduction that was supposed to observe it.
## Reproducer
### small.mlir
```mlir
memref.global "private" @g : memref<4xi32> = dense<[1, 2, 3, 4]>
func.func @f(%init: i32) -> i32 {
%c11 = arith.constant 11 : i32
%c7 = arith.constant 7 : i32
%a = memref.get_global @g : memref<4xi32>
affine.for %i = 0 to 4 {
%v = affine.load %a[%i] : memref<4xi32>
%x = arith.muli %v, %c11 : i32
affine.store %x, %a[%i] : memref<4xi32>
}
%b = memref.get_global @g : memref<4xi32>
%r1 = affine.for %i = 0 to 4 iter_args(%s = %init) -> (i32) {
%v = affine.load %b[%i] : memref<4xi32>
%t = arith.subi %s, %v : i32
affine.yield %t : i32
}
affine.for %i = 0 to 4 {
%v = affine.load %a[%i] : memref<4xi32>
%x = arith.addi %v, %c7 : i32
affine.store %x, %a[%i] : memref<4xi32>
}
%r2 = affine.for %i = 0 to 4 iter_args(%s = %r1) -> (i32) {
%v = affine.load %a[%i] : memref<4xi32>
%t = arith.subi %s, %v : i32
affine.yield %t : i32
}
return %r2 : i32
}
func.func @main() {
%z = arith.constant 0 : i32
%v = func.call @f(%z) : (i32) -> i32
vector.print %v : i32
return
}
```
### To reproduce:
```bash
$ mlir-opt small.mlir \
--lower-affine --convert-scf-to-cf --convert-vector-to-llvm \
--finalize-memref-to-llvm --convert-arith-to-llvm --convert-func-to-llvm \
--convert-cf-to-llvm --reconcile-unrealized-casts \
| mlir-runner -e main --entry-point-result=void \
--shared-libs=$LLVM_BUILD/lib/libmlir_c_runner_utils.so
-248
$ mlir-opt small.mlir --affine-loop-fusion \
--lower-affine --convert-scf-to-cf --convert-vector-to-llvm \
--finalize-memref-to-llvm --convert-arith-to-llvm --convert-func-to-llvm \
--convert-cf-to-llvm --reconcile-unrealized-casts \
| mlir-runner -e main --entry-point-result=void \
--shared-libs=$LLVM_BUILD/lib/libmlir_c_runner_utils.so
-148
```
### Actual Output:
```
-148
```
### Expected Output:
```
-248
```
## Root cause analysis
The dependence graph records accesses per memref *value* (`mlir/lib/Dialect/Affine/Analysis/Utils.cpp`):
```cpp
DenseMap> memrefAccesses;
```
and the edge it builds says so in its own comment (`mlir/include/mlir/Dialect/Affine/Analysis/Utils.h`):
```cpp
// The SSA value on which this edge represents a dependence.
// If the value is a memref, then the dependence is between graph nodes
// which contain accesses to the same memref 'value'.
```
Two `memref.get_global` operations on one symbol produce two distinct `Value`s, so no edge is created between a node accessing the buffer through one and a node accessing it through the other. The two loops appear independent and fusion is free to reorder them.
The dependence graph therefore misses dependences between accesses through distinct SSA values that alias the same storage. For this reproducer, a narrow fix would be to recognize `memref.get_global` operations referring to the same symbol when constructing the graph. More generally, the graph would need to account for memref aliasing rather than relying on `Value` identity alone.
Contributor guide
Research direction
Reproduce the failure with the supplied small.mlir pipeline and compare the results with and without --affine-loop-fusion. Read mlir/lib/Dialect/Affine/Analysis/Utils.cpp, especially the memrefAccesses map, alongside the dependence-edge comment in mlir/include/mlir/Dialect/Affine/Analysis/Utils.h. Done means the fusion pass preserves the dependence between the two memref.get_global handles and produces -248 for the reproducer.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp
- Domain
- compilers
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 55/100