[mlir][scf] emitNormalizedLoopBounds does not clamp the trip count at zero, so paired empty loops execute (3 callers)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Summary
`emitNormalizedLoopBounds` (`mlir/lib/Dialect/SCF/Utils/Utils.cpp`) computes a
normalized loop size as `ceilDiv(ub - lb, step)` with no lower clamp:
```c++
AffineExpr e = (s1 - s0).ceilDiv(s2);
normalizedLoopBounds.size =
affine::makeComposedFoldedAffineApply(rewriter, loc, e, {lb, ub, step});
```
and, on the non-constant path:
```c++
newUpperBound = rewriter.createOrFold(loc, diff, step);
```
`scf.for`'s contract defines the trip count as `max(0, ceil((ub - lb) / step))`.
An empty loop therefore has trip count **0**, but this helper yields a
**negative** raw size. When two such sizes are multiplied the signs cancel and
the flattened loop runs a positive number of times, executing a body the source
never executes.
Three in-tree transformations inherit it:
| caller | pass |
|---|---|
| `mlir::coalesceLoops` (`Utils.cpp:1018`) | `-affine-loop-coalescing` |
| `mlir::collapseParallelLoops` (`Utils.cpp:1190`) | parallel-loop collapsing |
| `mlir::normalizeForallOp` (`Utils.cpp:1604`) | `scf.forall` normalization |
Reproduces at `60b5f9a06722`.
## Reproducer
Both loops are empty: with `lb = 5, ub = 0, step = 2` the trip count is
`max(0, ceil(-5/2)) = 0`, so the body must never run and the result must be `0`.
The bounds are function arguments so the negative sizes are not statically
visible.
```mlir
func.func @count(%lb: index, %ub: index) -> i32 {
%c0 = arith.constant 0 : index
%c2 = arith.constant 2 : index
%one = arith.constant 1 : i32
%zero = arith.constant 0 : i32
%m = memref.alloca() : memref<1xi32>
memref.store %zero, %m[%c0] : memref<1xi32>
scf.for %i = %lb to %ub step %c2 {
scf.for %j = %lb to %ub step %c2 {
%o = memref.load %m[%c0] : memref<1xi32>
%n = arith.addi %o, %one : i32
memref.store %n, %m[%c0] : memref<1xi32>
}
}
%r = memref.load %m[%c0] : memref<1xi32>
return %r : i32
}
func.func @main() {
%lb = arith.constant 5 : index
%ub = arith.constant 0 : index
%r = func.call @count(%lb, %ub) : (index, index) -> i32
vector.print %r : i32
return
}
```
```
PIPE="-lower-affine -convert-scf-to-cf -convert-cf-to-llvm -convert-vector-to-llvm \
-finalize-memref-to-llvm -convert-func-to-llvm -convert-arith-to-llvm \
-reconcile-unrealized-casts"
mlir-opt $PIPE repro.mlir | mlir-runner -e main -entry-point-result=void \
--shared-libs=$LIB/libmlir_runner_utils.so
# => 0 (correct)
mlir-opt -affine-loop-coalescing $PIPE repro.mlir | mlir-runner -e main \
-entry-point-result=void --shared-libs=$LIB/libmlir_runner_utils.so
# => 4 (wrong: the body of an empty nest ran four times)
```
The generated bound makes the cancellation explicit:
```mlir
#map1 = affine_map<()[s0, s1] -> (((-s0 + s1) ceildiv 2) * ((-s0 + s1) ceildiv 2))>
scf.for %arg3 = %c0 to %3 step %c1 { ... }
```
`ceildiv(-5, 2) = -2` per loop, and `(-2) * (-2) = 4`.
### Second caller
`collapseParallelLoops` multiplies the same unclamped sizes:
```mlir
%0 = affine.apply #map()[%arg1, %arg2] // ceildiv(ub-lb, 2)
%1 = affine.apply #map()[%arg1, %arg2]
%2 = arith.muli %c1, %0 : index
%3 = arith.muli %2, %1 : index // product of two negatives
```
```
mlir-opt --test-scf-parallel-loop-collapsing="collapsed-indices-0=0,1" repro.mlir
```
### Note on static bounds
With *literal* constant bounds the defect is currently caught downstream —
`affine.delinearize_index` rejects a statically non-positive basis:
```
error: 'affine.delinearize_index' op no basis element may be statically non-positive
note: ... <{static_basis = array}>
```
That verifier check confirms the negative sizes are real, but it only fires when
the values are visible at compile time. With dynamic bounds the IR is
verifier-clean and the miscompilation is silent.
## Suggested fix
Clamp the normalized size at zero in `emitNormalizedLoopBounds`, so all three
callers inherit the fix:
```c++
AffineExpr e = (s1 - s0).ceilDiv(s2).max(0); // affine path
// and on the value path:
newUpperBound = rewriter.createOrFold(loc, newUpperBound, zero);
```
Note that the existing `ceilDivPositive` helper in the same file is **not** the
fix: it asserts a positive divisor and computes `(a + B - 1) / B`, which is still
negative for a negative dividend. The missing operation is the `max(0, ·)` that
`scf.for`'s own trip-count definition requires.
## Regression test
A test asserting that coalescing two empty loops produces a zero-trip loop, with
bounds passed dynamically so the `delinearize_index` verifier does not mask the
defect.
## Environment
* llvm-project at `60b5f9a06722`
* Release build with assertions, Linux x86-64
Contributor guide
Research direction
Start in mlir/lib/Dialect/SCF/Utils/Utils.cpp at emitNormalizedLoopBounds, then inspect its three callers: coalesceLoops, collapseParallelLoops, and normalizeForallOp. Reproduce the dynamic-bound case with the provided mlir-opt pipeline and add a regression test for two empty loops; done means the transformed loop has zero trips and the result remains 0.
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
- Clearly specified
- Newbie friendliness
- 68/100