[Bug tree-optimization/64308] New: Missed optimization: 64-bit divide used when 32-bit divide would work

[Bug tree-optimization/64308] New: Missed optimization: 64-bit divide used when 32-bit divide would work

[tavianator at gmail dot com]

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

            Bug ID: 64308
           Summary: Missed optimization: 64-bit divide used when 32-bit
                    divide would work
           Product: gcc
           Version: 4.9.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tavianator at gmail dot com

Created attachment 34280
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34280&action=edit
Test case

The following is a fairly typical implementation of exponentiation modulo m:

$ cat ipowm.c
// Computes (b**e) % m
unsigned int
ipowm(unsigned int b, unsigned int e, unsigned int m)
{
  unsigned int ret;
  b %= m;
  for (ret = m > 1; e; e >>= 1) {
    if ((e & 1) == 1) {
      ret = (unsigned long long)ret * b % m;
    }
    b = (unsigned long long)b * b % m;
  }
  return ret;
}

Unfortunately, GCC emits a 64-bit multiply and divide for both "... * b % m"
expressions on x86 and x86-64, where a 32-bit multiply and divide would be
equivalent and faster.

$ gcc -std=c11 -O3 -Wall -S -save-temps ipowm.c
$ cat ipowm.s
...
    imulq    %rdi, %rax
    divq    %rcx
...
    imulq    %rdi, %rax
    divq    %rcx
...

The pattern

    mull    %edi
    divl    %ecx

would be much faster.  They're equivalent because b is always reduced mod m, so
b < m and therefore (for any unsigned int x), x * b / m <= x * m / m == x, thus
the quotient will always fit in 32 bits.

[Bug tree-optimization/64308] Missed optimization: 64-bit divide used when 32-bit divide would work

[glisse at gcc dot gnu.org]

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

--- Comment #2 from Marc Glisse <glisse at gcc dot gnu.org> ---
You would need symbolic ranges, b and ret are in [0,m-1]. And then you are
using that very specific x86 instruction that divides 64 bits by 32 bits but
only works if the result fits in 32 bits. It works here because (m-1)*(m-1)/m<m
is small enough, but that's very hard for the compiler to prove, and I don't
know of another architecture with a similar instruction.

(Related: PR58897, PR53100)

[Bug tree-optimization/64308] Missed optimization: 64-bit divide used when 32-bit divide would work

[olegendo at gcc dot gnu.org]

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

Oleg Endo <olegendo at gcc dot gnu.org> changed:

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

--- Comment #4 from Oleg Endo <olegendo at gcc dot gnu.org> ---
(In reply to Marc Glisse from comment #2)
> You would need symbolic ranges, b and ret are in [0,m-1]. And then you are
> using that very specific x86 instruction that divides 64 bits by 32 bits but
> only works if the result fits in 32 bits. It works here because
> (m-1)*(m-1)/m<m is small enough, but that's very hard for the compiler to
> prove, and I don't know of another architecture with a similar instruction.

On SH a 64/32 -> 32 bit unsigned division can be done by repeating rotcl,div1
32 times (once for each result bit).  It's one of the examples for the 1-step
division insn 'div1' in the manuals.  Effectively it's the same as the x86 divl
insn.

[Bug tree-optimization/64308] Missed optimization: 64-bit divide used when 32-bit divide would work

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement