[mlir][scf] `transform.loop.unroll_and_jam` on `scf.for` jams across a carried memory dependence (miscompile)
- 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
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