[Bug tree-optimization/114341] New: Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[Bug tree-optimization/114341] New: Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[Explorer09 at gmail dot com]

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);
}
```

[Bug tree-optimization/114341] Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114341

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
x/(y&-y) is already recorded as PR 97738 .

[Bug tree-optimization/114341] Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114341

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2024-03-14
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1
           Keywords|                            |missed-optimization
                 CC|                            |pinskia at gcc dot gnu.org
           Severity|normal                      |enhancement

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed for the multiply as I mentioned the divide is already recorded.

[Bug tree-optimization/114341] Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[Explorer09 at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114341

--- Comment #3 from Kang-Che Sung <Explorer09 at gmail dot com> ---
I missed one case that is more obvious:
(1 << __builtin_ctz(y)) == (y & -y)

Multiplication is not needed in this case, and thus (1 << __builtin_ctz(y)) can
simplify to (y & -y). (I didn't think of a reason we need to optimize the other
way around for this special case.)

[Bug tree-optimization/114341] Optimization opportunity with {mul,div} "(x & -x)" and {<<,>>} "ctz(x)"

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=114341

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Kang-Che Sung from comment #3)
> I missed one case that is more obvious:
> (1 << __builtin_ctz(y)) == (y & -y)
> 
> Multiplication is not needed in this case, and thus (1 << __builtin_ctz(y))
> can simplify to (y & -y). (I didn't think of a reason we need to optimize
> the other way around for this special case.)

Well __builtin_ctz(y) is not well defined for y==0. But maybe that is ok here.