[Bug middle-end/114660] New: Exponentiating by squaring not performed for x * y * y * y * y

[Bug middle-end/114660] New: Exponentiating by squaring not performed for x * y * y * y * y

[antoshkka at gmail dot com]

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

            Bug ID: 114660
           Summary: Exponentiating by squaring not performed for x * y * y
                    * y * y
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: antoshkka at gmail dot com
  Target Milestone: ---

For the following code:

int mul(int x, int y) {
    return x * y * y * y * y;
}


with -O2 GCC produces the frollowing assembly:

mul(int, int):
  mov eax, edi
  imul eax, esi
  imul eax, esi
  imul eax, esi
  imul eax, esi
  ret


However, a more optimal code could be generated with less multiplications:

mul(int, int):
        mov     eax, edi
        imul    esi, esi
        imul    eax, esi
        imul    eax, esi
        ret

Godbolt playground: https://godbolt.org/z/6dP11jPfx

[Bug middle-end/114660] Exponentiating by squaring not performed for x * y * y * y * y

[antoshkka at gmail dot com]

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

--- Comment #1 from Antony Polukhin <antoshkka at gmail dot com> ---
The above godbolt link for an old version of GCC, here's for 14.0
https://godbolt.org/z/dTPYY1T9W

[Bug tree-optimization/114660] Exponentiating by squaring not performed for x * y * y * y * y

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
          Component|middle-end                  |tree-optimization

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
We don't do as much reassociation as we should with signed integers due to
overflow. If you use -fwrapv, you get the reassociation; I am 99% sure there is
a dup for this bug too.

[Bug tree-optimization/114660] Exponentiating by squaring not performed for x * y * y * y * y

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-04-09
     Ever confirmed|0                           |1

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> We don't do as much reassociation as we should with signed integers due to
> overflow. If you use -fwrapv, you get the reassociation; I am 99% sure there
> is a dup for this bug too.

I should say we also do it for unsigned already (see PR 95867), -fwrapv case we
just treat signed similar to unsigned here. Anyways what needs to happen is we
need 2 levels of gimple, one with signed integer overflow behavior and then one
with wrapping behavior. RTL does not distinguish between signed and unsigned
behaviors for many operations (plus and multiple) so we get some optimizations
there but not all.

[Bug tree-optimization/114660] Exponentiating by squaring not performed for x * y * y * y * y

[jakub at gcc dot gnu.org]

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think we've been discussing an idea of turning on flag_wrapv very late among
the GIMPLE passes and reassociate again.  Because RTL also kind of assumes
flag_wrapv, there is no difference between signed/unsigned
addition/subtraction/non-widening multiplication.
Though, a question is if it wouldn't screw up range info for use during
expansion too much.  Other option is to rewrite into unsigned operations only
what we've successfully reassociated in the late reassoc pass.

[Bug tree-optimization/114660] Exponentiating by squaring not performed for x * y * y * y * y

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> ---
For the case in question when x is zero then y can be INT_MAX and thus y * y
already overflow. But x * y * y * y * y * y could be associated as
(x * y) * (y^4).