[Bug tree-optimization/97997] New: Missed optimization: Multiply of extended integer cannot overflow

[Bug tree-optimization/97997] New: Missed optimization: Multiply of extended integer cannot overflow

[matthijs at stdin dot nl]

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

            Bug ID: 97997
           Summary: Missed optimization: Multiply of extended integer
                    cannot overflow
           Product: gcc
           Version: 10.2.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: matthijs at stdin dot nl
  Target Milestone: ---

When an integer is extended and then multiplied by another integer of the
original size, the resulting multiplication can never overflow. However, gcc
does not seem to realize this. Consider:

uint16_t calc_u(uint16_t x ) {
        return (uint32_t)x * 10 / 10;
}

If gcc would realize that x * 10 cannot overflow, it can optimize away the * 10
/ 10. However, it does not:

$ gcc-10 -Os -Wall -Wextra -pedantic foo.c && objdump -S --disassemble=calc_u
a.out
00000000000011a0 <calc_u>:
    11a0:       f3 0f 1e fa             endbr64 
    11a4:       0f b7 c7                movzwl %di,%eax
    11a7:       b9 0a 00 00 00          mov    $0xa,%ecx
    11ac:       31 d2                   xor    %edx,%edx
    11ae:       6b c0 0a                imul   $0xa,%eax,%eax
    11b1:       f7 f1                   div    %ecx
    11b3:       c3                      retq   

When doing the multiplication signed, this optimization *does* happen:

uint16_t calc_s(uint16_t x ) {
        return (int32_t)x * 10 / 10;
}

$ gcc-10 -Os -Wall -Wextra -pedantic foo.c  && objdump -S --disassemble=calc_s
a.out

0000000000001199 <calc_s>:
    1199:       f3 0f 1e fa             endbr64 
    119d:       89 f8                   mov    %edi,%eax
    119f:       c3                      retq   

Since signed overflow is undefined, gcc presumably assumes that the
multiplication does not overflow and optimizes this. This shows that the
machinery for this optimization exists and works and suggests that the only
thing missing in the unsigned case is realizing that the overflow cannot
happen.

The above uses 16/32bit numbers, but the same happens on 32/64bit (just not on
8/16 bit, because then things are integer-promoted and multiplication is always
signed). When using -O2 or -O3, the code generated for unsigned is different,
but still not fully optimized.

Maybe I'm missing some corner case of the C language that would make this
optimization incorrect, but I think it should be allowed.

The original code that triggered this report is:

#define ticks2us(t)   (uint32_t)((uint64_t)(t)*1000000 / TICKS_PER_SEC)

Which could be optimized to a single multiply or even bitshift rather than a
multiply and division for particular values of TICKS_PER_SEC, while staying
generally applicable (but slower) for other values.

I took a guess at the component, please correct that if needed.

$ gcc-10 --version
gcc-10 (Ubuntu 10.2.0-5ubuntu1~20.04) 10.2.0
Copyright (C) 2020 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
unsigned short
f1 (unsigned short x)
{
  return x * 10 / 10;
}

unsigned short
f2 (unsigned short x)
{
  int a = x;
  int b = 10;
  int c = 10;
  return a * b / c;
}

unsigned short
f3 (unsigned short x)
{
  return x * 10U / 10;
}

unsigned short
f4 (unsigned short x)
{
  unsigned a = x;
  unsigned b = 10;
  unsigned c = 10;
  return a * b / c;
}

For f1 we fold it already during generic folding, f2 we fold during ccp using
the
/* Simplify (t * 2) / 2) -> t.  */
(for div (trunc_div ceil_div floor_div round_div exact_div)
 (simplify
  (div (mult:c @0 @1) @1)
  (if (ANY_INTEGRAL_TYPE_P (type)
       && TYPE_OVERFLOW_UNDEFINED (type))
   @0)))
rule.

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |jakub at gcc dot gnu.org
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2020-11-25

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Created attachment 49629
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=49629&action=edit
gcc11-pr97997.patch

Untested fix.

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[cvs-commit at gcc dot gnu.org]

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

--- Comment #3 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Jakub Jelinek <jakub@gcc.gnu.org>:

https://gcc.gnu.org/g:a3ebc13492ff238873f2c6a7a3e51abefec1d052

commit r11-5444-ga3ebc13492ff238873f2c6a7a3e51abefec1d052
Author: Jakub Jelinek <jakub@redhat.com>
Date:   Thu Nov 26 16:24:07 2020 +0100

    match.pd: Use ranges to optimize some x * y / y to x [PR97997]

    For signed integers with undefined overflow we already optimize x * y / y
    into x, but for signed integers with -fwrapv or unsigned integers we don't.
    The following patch allows optimizing that into just x if value ranges
    prove that x * y will never overflow.
    It uses the global SSA_NAME_RANGE_INFO only, because like mentioned
    in another PR we don't currently have a way to tell the ranger from
match.pd
    the use stmt (and we'd need in that case to tell ranger to only follow
    SSA_NAME_DEF_STMTs + SSA_NAME_RANGE_INFO and never go in the other
    direction, as following immediate uses seems forbidden in match.pd).
    Another possibility would be to optimize this during vrp, but on the
    other side the optimization itself is match.pd-ish.

    2020-11-26  Jakub Jelinek  <jakub@redhat.com>

            PR tree-optimization/97997
            * match.pd ((t * 2) / 2) -> t): Optimize even for defined
            overflow if ranges prove there is no overflow.

            * gcc.dg/tree-ssa/pr97997-1.c: New test.
            * gcc.dg/tree-ssa/pr97997-2.c: New test.

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Fixed for 11.1+.

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[matthijs at stdin dot nl]

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

--- Comment #5 from Matthijs Kooijman <matthijs at stdin dot nl> ---
Awesome, thanks for the quick response and fix!

[Bug tree-optimization/97997] Missed optimization: Multiply of extended integer cannot overflow

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |11.0
           Keywords|                            |missed-optimization
           Severity|normal                      |enhancement