llvm / llvm/llvm-project

[mlir][scf] `transform.loop.unroll_and_jam` on `scf.for` jams across a carried memory dependence (miscompile)

Open
#198,266 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

`transform.loop.unroll_and_jam` performs unroll-and-jam on an `scf.for`
with no memory-dependence legality check, so it will jam a nest whose
loop-carried dependence is violated by the new iteration order,
producing IR that computes a different result. No diagnostic is emitted.

`transform::LoopUnrollAndJamOp::applyToOne`
(`mlir/lib/Dialect/SCF/TransformOps/SCFTransformOps.cpp:410`) routes
`scf.for` to `mlir::loopUnrollJamByFactor(scf::ForOp, …)`
(`mlir/lib/Dialect/SCF/Utils/Utils.cpp`), which gates only on
`areInnerBoundsInvariant`, an iter-args/results check, and trip-count
divisibility — it performs no dependence analysis. The op's tablegen
description does not state that legality is the caller's responsibility;
unroll-and-jam is classically a dependence-gated transformation, so this
is a soundness gap. (The affine overload at line 418 has the same gap;
filed separately, as the SCF path has no affine dependence analysis to
reuse.)

### Reproducer

Input — the inner statement is `arr[i, j] = arr[i-1, j+1]`, a nest
carrying the flow dependence `source=(i, j)` → `destination=(i+1, j-1)`,
distance vector `(1, -1)`:

```mlir
module attributes {transform.with_named_sequence} {
func.func @stencil(%arr: memref<5x5xi32>) {
%c0 = arith.constant 0 : index
%c1 = arith.constant 1 : index
%c4 = arith.constant 4 : index
%c5 = arith.constant 5 : index
scf.for %i = %c1 to %c5 step %c1 {
scf.for %j = %c0 to %c4 step %c1 {
%im1 = arith.subi %i, %c1 : index
%jp1 = arith.addi %j, %c1 : index
%v = memref.load %arr[%im1, %jp1] : memref<5x5xi32>
memref.store %v, %arr[%i, %j] : memref<5x5xi32>
}
} {unrolljam}
return
}
transform.named_sequence @__transform_main(%root: !transform.any_op {transform.readonly}) {
%f = transform.structured.match ops{["scf.for"]} attributes{unrolljam} in %root
: (!transform.any_op) -> !transform.any_op
transform.loop.unroll_and_jam %f { factor = 2 } : !transform.any_op
transform.yield
}
}
```

`mlir-opt --transform-interpreter` produces (canonicalized for
readability):

```mlir
scf.for %i = %c1 to %c5 step %c2 {
scf.for %j = %c0 to %c4 step %c1 {
%0 = arith.subi %i, %c1 : index
%1 = arith.addi %j, %c1 : index
%2 = memref.load %arr[%0, %1] : memref<5x5xi32> // arr[i-1, j+1]
memref.store %2, %arr[%i, %j] : memref<5x5xi32> // arr[i, j] = ...
%3 = arith.addi %i, %c1 : index
%4 = memref.load %arr[%i, %1] : memref<5x5xi32> // arr[i, j+1] <-- stale
memref.store %4, %arr[%3, %j] : memref<5x5xi32> // arr[i+1, j] = ...
}
}
```

The bug is visible in this IR alone: the jammed `i+1` body reads
`%arr[%i, %j+1]` at inner index `j`, but the `i` body only writes
`%arr[%i, %j+1]` at inner index `j+1` (a *later* inner iteration). In
the original nest row `i` is fully written before any of row `i+1` is
read; after jamming, the `i+1` read sees the still-initial value of
`%arr[i, j+1]`. The two programs therefore compute different arrays.

(Confirmed end-to-end with `mlir-runner` on a `@main` that fills
`arr[i,j] = 10*i+j`: rows 2–4 of the printed buffer differ between the
baseline and the jammed program. That harness is omitted here since the
reordering is already evident from the IR; available on request.)

### Environment

- Upstream `main` merge-base `c48b74fbcf604c14f4e53d284c3f3da4076db427`.
- Homebrew LLVM 22.1.4 `mlir-opt` (same behavior).

Contributor guide

Open the contributing guide

Research direction

Start in mlir/lib/Dialect/SCF/TransformOps/SCFTransformOps.cpp at LoopUnrollAndJamOp::applyToOne and follow the scf.for path into mlir/lib/Dialect/SCF/Utils/Utils.cpp. Run the supplied reproducer with mlir-opt --transform-interpreter and inspect the canonicalized IR. Done means the transformation no longer silently produces incorrect results for the carried-dependence case, with the legality behavior reflected in the relevant operation description or tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
compilers
Issue type
Bug
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.