Issue 241891
Summary [mlir][math] math-expand-ops computes math.ctlz wrongly for widths that are not a power of two
Labels mlir
Assignees
Reporter 0z5a
    The math.ctlz expansion in -math-expand-ops returns wrong counts for integer types whose width is not a power of two. For example ctlz(1 : i7) gives 4 instead of 6, and ctlz(1 : i24) gives 22 instead of 23.

Reproducer (the input is a function argument, so the constant folder does not run):

```mlir
func.func @ctlz_i7(%a : i7) {
  %r = math.ctlz %a : i7
 vector.print %r : i7
  return
}
func.func @ctlz_i24(%a : i24) {
  %r = math.ctlz %a : i24
  vector.print %r : i24
  return
}
func.func @main() {
  %c1_i7 = arith.constant 1 : i7
  call @ctlz_i7(%c1_i7) : (i7) -> ()
 %c1_i24 = arith.constant 1 : i24
  call @ctlz_i24(%c1_i24) : (i24) -> ()
 return
}
```

```
mlir-opt repro.mlir -pass-pipeline="builtin.module(func.func(math-expand-ops),convert-vector-to-scf,convert-scf-to-cf,convert-vector-to-llvm,convert-to-llvm,reconcile-unrealized-casts)" \
  | mlir-runner -e main -entry-point-result=void -shared-libs=libmlir_c_runner_utils.so -shared-libs=libmlir_runner_utils.so
```

Output on main (b02e25dc58dc, x86_64 Linux): `4` and `22`. Without math-expand-ops (math.ctlz lowered to llvm.intr.ctlz) the same program prints `6` and `23`, and the math.ctlz constant folder also gives 6 and 23.

The expansion is a binary search whose steps are bitwidth/2, bitwidth/4, and so on (ExpandOps.cpp, convertCtlzOp). For a power-of-two width these steps can add up to any count below the width, but for other widths they cannot: i24 gets 12 + 6 + 3 + 1 = 22, so 23 is unreachable, and i7 gets 3 + 1 = 4. Checking every input exhaustively, the expansion is wrong for 1/8 inputs of i3, 19/128 of i7, 585/4096 of i12 and 4903/32768 of i15, and correct for i2, i4, i8 and i16.

This is a regression from LLVM 16, which expanded ctlz with an scf.while loop. The binary search came in with 711c58938 ("[mlir][math] Update math arith expansions for vectorization"), so LLVM 17 and later are affected.

Starting the search at the largest power of two below the width (16, 8, 4, 2, 1 for i24) fixes it, and produces the same IR as now for power-of-two widths.

A fix with a regression test is ready. I can open a pull request for it.

Assisted-by: Claude (claude-opus-5-5). I reviewed the change and this text.

_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs

Reply via email to