[InstCombine] Fold a zero-select hexadecimal digit count into ctlz(x | 1)
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
InstCombine does not currently fold the following pattern:
```llvm
declare i64 @llvm.ctlz.i64(i64, i1 immarg)
define i64 @hex_digits_src(i64 noundef %x) {
%iszero = icmp eq i64 %x, 0
%lz = call i64 @llvm.ctlz.i64(i64 %x, i1 true)
%bias = sub nuw nsw i64 67, %lz
%digits = lshr i64 %bias, 2
%result = select i1 %iszero, i64 1, i64 %digits
ret i64 %result
}
```
into:
```llvm
declare i64 @llvm.ctlz.i64(i64, i1 immarg)
define i64 @hex_digits_tgt(i64 noundef %x) {
%nonzero = or i64 %x, 1
%lz = call i64 @llvm.ctlz.i64(i64 %nonzero, i1 true)
%bias = sub nuw nsw i64 67, %lz
%digits = lshr i64 %bias, 2
ret i64 %digits
}
```
For non-zero values, setting the least significant bit does not change the number of leading zeros:
```text
ctlz(x | 1) == ctlz(x), when x != 0
```
For `x == 0`, `x | 1` becomes `1`:
```text
ctlz(1) = 63
(67 - 63) >> 2 = 1
```
This matches the value returned by the original `select` expression.
Therefore, for a defined i64 value — in particular, when x is known not to be undef or poison — replacing the explicit zero
comparison and select with ctlz(x | 1) preserves the result.
## Code generation improvement
The current and expected forms were compiled using LLVM trunk.
| Metric | Current form | Expected form | Change |
|---|---:|---:|---:|
| Machine instructions per iteration | 7 | 5 | 2 fewer (`-28.6%`) |
| µOps per iteration | 8 | 5 | 3 fewer (`-37.5%`) |
| Block reciprocal throughput | 2.0 cycles | 1.3 cycles | 0.7 cycles lower (`-35.0%`) |
## Verification
Alive2: https://alive2.llvm.org/ce/z/rF6YMe
Compiler-explorer sample & perf: https://compiler-explorer.com/z/K7hrT76rn
Contributor guide
Assessment
This issue has not been assessed yet.