https://gcc.gnu.org/bugzilla/show_bug.cgi?id=122005
Bug ID: 122005
Summary: Optimization: recognize common isPowerOf2 idiom
Product: gcc
Version: 15.1.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: Explorer09 at gmail dot com
Target Milestone: ---
GCC has implemented the C23 function stdc_has_single_bit() as a builtin. This
is good, but before that C standard function, many programs resolve to this
idiom for determining whether an unsigned integer is a power of 2:
```c
(x > 0) && (x & (x - 1) == 0)
```
A proof that this idiom is still used is in Linux kernel:
https://elixir.bootlin.com/linux/v6.16.7/source/include/linux/log2.h#L45
and the "Bit Twiddling Hacks" page (I know it's not updated for years, but many
people still refer to it)
https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
GCC and Glibc implement the function as:
```c
(x ^ (x - 1)) > x - 1
```
GCC also has a special case of using `x & (x - 1) == 0` if `x` is known to be
nonzero.
And yet it doesn't recognize the `(x > 0) && (x & (x - 1) == 0)` idiom above
and optimize accordingly, hence this feature request.
1. In x86-64, convert the idiom `(x > 0) && (x & (x - 1) == 0)` to `(x ^ (x -
1)) > x - 1`. The latter can make smaller code size.
2. Ditto for RISC-V targets. The `(x ^ (x - 1)) > x - 1` version has smaller
code size.
3. For ARM and AArch64, with CBZ instruction support, it seems that both `(x >
0) && (x & (x - 1) == 0)` and `(x ^ (x - 1)) > x - 1` versions produce same
code size, so I can't tell which version is better.
Test code
```c
#include <stdbool.h>
#if __has_builtin(__builtin_stdc_has_single_bit)
bool is_power_of_2(unsigned int x) {
return __builtin_stdc_has_single_bit(x);
}
bool is_zero_or_power_of_2(unsigned int x) {
if (x == 0)
__builtin_unreachable();
return __builtin_stdc_has_single_bit(x);
}
#endif
bool is_power_of_2_impl(unsigned int x) {
return (x ^ (x - 1)) > x - 1;
}
bool is_power_of_2_idiom(unsigned int x) {
return x != 0 && (x & (x - 1)) == 0;
}
bool is_zero_or_power_of_2_impl(unsigned int x) {
if (x == 0)
__builtin_unreachable();
return x != 0 && (x & (x - 1)) == 0;
}
```
Assembly produced by ARM64 GCC 15.2.0 with `-Os` option (in Compiler Explorer)
```assembly
is_power_of_2_impl:
sub w1, w0, #1
eor w0, w1, w0
cmp w1, w0
cset w0, cc
ret
is_power_of_2_idiom:
cbz w0, .L5
sub w1, w0, #1
tst w1, w0
cset w0, eq
.L5:
ret
```
