[Bug tree-optimization/94757] New: GCC does not optimise unsigned multiplication known not to overflow

[Bug tree-optimization/94757] New: GCC does not optimise unsigned multiplication known not to overflow

[felix.von.s at posteo dot de]

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

            Bug ID: 94757
           Summary: GCC does not optimise unsigned multiplication known
                    not to overflow
           Product: gcc
           Version: 10.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: felix.von.s at posteo dot de
  Target Milestone: ---

This code:

    #include <limits.h>

    unsigned f(unsigned x) {
        if (x > UINT_MAX / 3)
            __builtin_unreachable();
        return (x * 3) / 3;
    }

should be possible to optimise into the identity function, but (on x86_64) gcc
-O3 generates a multiplication (via LEA) then a division (via multiplication).
GCC knows that the multiplication cannot overflow, because replacing the
returned expression with __builtin_mul_overflow_p(x, 3, x) is makes it optimise
to returning constant 0.

[Bug tree-optimization/94757] GCC does not optimise unsigned multiplication known not to overflow

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-04-27
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.

[Bug tree-optimization/94757] GCC does not optimise unsigned multiplication known not to overflow

[qianjh at cn dot fujitsu.com]

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

Qian Jianhua <qianjh at cn dot fujitsu.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |qianjh at cn dot fujitsu.com

--- Comment #2 from Qian Jianhua <qianjh at cn dot fujitsu.com> ---
>GCC knows that the multiplication cannot overflow, because replacing the 
>returned expression with __builtin_mul_overflow_p(x, 3, x) is makes it optimise 
>to returning constant 0.
__builtin_mul_overflow_p function only check the value range. So it could be
optimised by VRP.

The process like this
   x     range [0, UINT_MAX/3]
   x*3   range [0, UINT_MAX]
   x*3/3 range [0, UINT_MAX/3], but not calculate the result(=x).

I tested some other cases. 
It seems that the optimiser in gcc only check the value range of the
expression, but not track/calculate the result of the expression, if the
variable is not constant int the expression.


So i think such optimisation of expression is not supported in gcc now.

In clang, the expression "(x * 3) / 3" is optimised to "x".

[Bug tree-optimization/94757] GCC does not optimise unsigned multiplication known not to overflow

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0
           Severity|normal                      |enhancement
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=97997
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed for GCC 11 by r11-5444-ga3ebc13492ff23 (PR 97997), this is almost a dup
of bug 97997 but not exactly.