llvm / llvm/llvm-project

Missed optimization of ctzg when operating on less than C's int prec due to zext.

Open
#218,231 2 comments 0 reactions 1 assignee Claimed by @OmarAzizi View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

[Clang trunk](https://godbolt.org/z/915G1xxYq)
-O2 for C produce the following LLVM:

```c
typedef unsigned short u16;
typedef unsigned u32;

int
clzu32_bitreverse_u16 (u16 x)
{
int lhs = __builtin_clz (__builtin_bitreverse16 (x));
int rhs = __builtin_ctzg (x) + 16;
return lhs == rhs;
}
```

```llvm
define dso_local range(i32 0, 2) i32 @clzu32_bitreverse_u16(i16 noundef zeroext %x) local_unnamed_addr {
entry:
%0 = tail call i16 @llvm.bitreverse.i16(i16 %x)
%conv = zext i16 %0 to i32
%1 = tail call range(i32 16, 33) i32 @llvm.ctlz.i32(i32 %conv, i1 true)
%2 = tail call range(i16 0, 17) i16 @llvm.cttz.i16(i16 %x, i1 true)
%3 = or disjoint i16 %2, 16
%add = zext nneg i16 %3 to i32
%cmp = icmp eq i32 %1, %add
%conv1 = zext i1 %cmp to i32
ret i32 %conv1
}

declare i16 @llvm.bitreverse.i16(i16) #1

declare i32 @llvm.ctlz.i32(i32, i1 immarg) #2

declare i16 @llvm.cttz.i16(i16, i1 immarg) #2
```

This does not optimize to return 1 because of:
%conv = zext i16 %0 to i32
...
%add = zext nneg i16 %3 to i32

[I notice this](https://gcc.gnu.org/pipermail/gcc-patches/2026-August/728596.html) while working on GCC optimizing clz (bitreverse) -> ctz and vice versa.
The patch optimize this whole original code:
```c
typedef unsigned short u16;
typedef unsigned _BitInt(24) u24;
typedef unsigned u32;
typedef unsigned _BitInt(48) u48;

int
clzu16_bitreverse_u16 (u16 x)
{
int lhs = __builtin_clzg (__builtin_bitreverse16 (x));
int rhs = __builtin_ctzg (x);
return lhs == rhs;
}

int
clzu24_bitreverse_u24 (u24 x)
{
int lhs = __builtin_clzg (__builtin_bitreverseg (x));
int rhs = __builtin_ctzg (x);
return lhs == rhs;
}

int
clzu32_bitreverse_u16 (u16 x)
{
int lhs = __builtin_clz (__builtin_bitreverse16 (x));
int rhs = __builtin_ctzg (x) + 16;
return lhs == rhs;
}

int
clzu32_bitreverse_u32 (u32 x)
{
int lhs = __builtin_clz (__builtin_bitreverse32 (x));
int rhs = __builtin_ctz (x);
return lhs == rhs;
}

int
clz48_bitreverse_u48 (u48 x)
{
int lhs = __builtin_clzg (__builtin_bitreverseg (x));
int rhs = __builtin_ctzg (x);
return lhs == rhs;
}

int
clzu64_bitreverse_u32 (u32 x)
{
int lhs = __builtin_clzll (__builtin_bitreverse32 (x));
int rhs = __builtin_ctzg (x) + 32;
return lhs == rhs;
}
```

Note that GCC returns int for __builtin_ctzg as [documented](https://gcc.gnu.org/onlinedocs/gcc/Bit-Operation-Builtins.html).

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.