[InstCombine] Missed `ctlz(..., true)` zero-select fold through narrowing arithmetic
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
## Summary
LLVM can canonicalize some `ctlz(x, true)` plus `select x == 0` patterns into a
branchless `ctlz(x, false)` expression, but it misses the same idea when the
`ctlz.i64` result is used through arithmetic, narrowed to `i32`, selected with
zero, and then added to a base.
This matters for integer digit-count idioms such as:
```text
digits = ceil(active_bits(x) / 4)
= (bitwidth(x) - ctlz(x) + 3) >> 2
```
When `x == 0`, `ctlz(x, false) == bitwidth`, so the same arithmetic naturally
produces zero and the explicit `icmp/select` can be removed.
## Missed Pattern
```llvm
declare i64 @llvm.ctlz.i64(i64, i1 immarg)
define i32 @src_i64_base(i64 %x, i32 %base) {
entry:
%iszero = icmp eq i64 %x, 0
%lz = call i64 @llvm.ctlz.i64(i64 %x, i1 true)
%biased = sub nuw nsw i64 67, %lz
%digits64 = lshr i64 %biased, 2
%digits = trunc nuw nsw i64 %digits64 to i32
%digits.phi = select i1 %iszero, i32 0, i32 %digits
%result = add i32 %digits.phi, %base
ret i32 %result
}
```
## Expected Result
The `i64` form could be normalized to:
```llvm
define i32 @src_i64_base(i64 %x, i32 %base) {
entry:
%lz = call i64 @llvm.ctlz.i64(i64 %x, i1 false)
%biased = sub nuw nsw i64 67, %lz
%digits64 = lshr i64 %biased, 2
%digits = trunc nuw nsw i64 %digits64 to i32
%result = add i32 %digits, %base
ret i32 %result
}
```
The analogous direct `i32` form is already folded this way. The missed case is
the `i64` expression being narrowed to `i32` before the select/base-add use.
## Why This Should Be Legal
For the missed case:
```text
digits = (67 - ctlz.i64(x)) >> 2
```
If `x != 0`, `ctlz(x, true)` and `ctlz(x, false)` are identical.
If `x == 0`, the original expression's false arm may be poison because
`ctlz(x, true)` is poison, but that arm is not selected. The selected value is
zero.
With `ctlz(x, false)`, `ctlz(0, false) == 64`, so:
```text
(67 - 64) >> 2 = 3 >> 2 = 0
```
This matches the selected zero value, allowing the explicit zero check and
select to be removed.
This reasoning is not specific to the constant `67`; it applies to the
`ceil(active_bits / 2^k)` family where the arithmetic is arranged so that
`ctlz(0, false)` maps to the same zero result selected by the original code.
## Motivation
This normalization would make downstream idiom recognition easier. A separate
shift-count loop transform can generate or expose `ctlz(..., true)` plus a
zero-select form for prechecked loops. If InstCombine normalizes that into
`ctlz(..., false)` when the arithmetic already produces zero for zero input,
the loop transform can support both `i32` and `i64` digit-count forms with a
cleaner canonical target.
It also avoids penalizing `i64 + base` forms. The current shape keeps an
extra `icmp/select` in IR, while the normalized form is a compact fixed-cost
expression on targets with cheap `clz`/`lzcnt`.
For the normalized `i64 + base` expression, representative backend output is:
| target | current zero-select shape | normalized `ctlz(false)` shape | effect |
| --- | --- | --- | --- |
| x86-64 with `lzcnt` | `lzcntq; sub; shr; test; cmov; add` | `lzcntq; sub; shr; add` | removes the explicit zero test and `cmov` |
| AArch64 | `clz; cmp; sub; lsr; csel; add` | `clz; sub; add ..., lsr #2` | removes `cmp`/`csel` and folds the shift into the add |
| RISC-V with Zbb | `seqz; clz; sub; srli; mask; addw` | `clz; sub; srli; addw` | removes the zero-mask sequence |
| ARMv7 | two-half `clz` plus conditional zero handling | two-half `clz` sequence | smaller, but still less compact than native 64-bit targets |
This is materially better than preserving the zero-test/select shape, which
can lower to extra `cmov`/`csel` or equivalent zero-handling code.
## Notes
- This should be guarded by proof that the replacement expression evaluates to
the selected zero value when `ctlz(x, false) == bitwidth(x)`.
- The direct `i32` variant is already handled; the missed case involves the
`i64` expression being narrowed to `i32` and then combined with a base.
- This issue is independent from introducing a loop idiom transform; it is a
canonicalization opportunity for IR that already contains `ctlz`.
AliveProof :https://alive2.llvm.org/ce/z/uySgb9
Compiler-explorer sample & perf : https://compiler-explorer.com/z/zbP31PdcE
Contributor guide
Assessment
This issue has not been assessed yet.