llvm / llvm/llvm-project

[InstCombine] Missed `ctlz(..., true)` zero-select fold through narrowing arithmetic

Open
#202,078 7 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
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

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.