llvm / llvm/llvm-project

[MLIR][Affine] Miscompilation: `affine-loop-fusion` misses the dependence between two memref.get_global handles to the same buffer

Open
#216,535 4 comments 0 reactions 0 assignees View on GitHub
miscompilation mlir
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.