llvm / llvm/llvm-project

[mlir][scf] emitNormalizedLoopBounds does not clamp the trip count at zero, so paired empty loops execute (3 callers)

Open
#223,231 2 comments 0 reactions 0 assignees View on GitHub
mlir:scf
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

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.