https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114341
Bug ID: 114341
Summary: Optimization opportunity with {mul,div} "(x & -x)" and
{<<,>>} "ctz(x)"
Product: gcc
Version: 13.2.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: ---
This is an optimization opportunity that I'm not sure it's worth
implementing in gcc, since I only used the (x / (x & -x)) pattern on
compile time constants only.
When x and y are unsigned integers and the value of y is non-zero,
then (x / (y & -y)) and (x >> __builtin_ctz(y)) are equivalent.
Similarly, (x * (y & -y)) and (x << __builtin_ctz(y)) are equivalent.
One reason for using the (x / (y & -y)) pattern is that it's more
portable among C compilers before C23 made a standard "CTZ" API
(stdc_trailing_zeros) for everyone. Even though we have
stdc_trailing_zeros() now, the (x / (y & -y)) pattern is still useful
for constant expressions when stdc_trailing_zeros() might not be a
compiler built in.
Processors that support CTZ instructions would optimize (x / (y & -y))
to (x >> __builtin_ctz(y)); processors that do not support CTZ would
optimize the other way around. (I know RISC-V might need the latter
way of optimization.)
```c
unsigned int func1a(unsigned int x, unsigned int y) {
if (y == 0)
return -1; /* placeholder value to indicate error */
return x / (y & -y);
}
unsigned int func1b(unsigned int x, unsigned int y) {
if (y == 0)
return -1; /* placeholder value to indicate error */
return x >> __builtin_ctz(y);
}
unsigned int func2a(unsigned int x, unsigned int y) {
if (y == 0)
return -1; /* placeholder value to indicate error */
return x * (y & -y);
}
unsigned int func2b(unsigned int x, unsigned int y) {
if (y == 0)
return -1; /* placeholder value to indicate error */
return x << __builtin_ctz(y);
}
```
