llvm / llvm/llvm-project

[InstCombine] Fold a zero-select hexadecimal digit count into ctlz(x | 1)

Open
#214,416 0 comments 0 reactions 1 assignee Claimed by @JihyeonJeong129 View on GitHub
llvm:instcombine missed-optimization
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.