[Bug c/105521] New: missed optimization in modulo arithmetic

[Bug c/105521] New: missed optimization in modulo arithmetic

[goswin-v-b at web dot de]

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

            Bug ID: 105521
           Summary: missed optimization in modulo arithmetic
           Product: gcc
           Version: 11.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: goswin-v-b at web dot de
  Target Milestone: ---

I'm trying to compute (a*a)%n for uint64_t types on x86_64 using "gcc -O2 -W
-Wall" like this:

  #include <stdint.h>
  #include <assert.h>

  uint64_t sqrmod(uint64_t a, uint64_t n) {
    assert(a < n);
    unsigned __int128 x = a;
    x *= a;
    return x % n;
  }

I expected to get the following code:

  sqrmod:
        cmpq    %rsi, %rdi
        jnb     .L13         // assert(a < n) failure
        movq    %rdi, %rax
        mul     %rdi
        div     %rsi
        movq    %rdx, %rax
        ret

The compiler does get the "mul" right but instead of the "div" it throws in a
call to "__umodti3". The "__umodti3" function is horribly long code that will
be worlds slower than a simple div.

Note: The "asset(a < n);" should tell the compiler that the "div" instruction
can not overflow and will not cause a #DivisionError. Without the assert the
compiler could (conditionally) add "a %= n;" for the same effect.

https://godbolt.org/z/cd57Wd4oo

[Bug target/105521] missed optimization in modulo arithmetic

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|middle-end                  |target
             Target|                            |x86_64-*-*

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
This requires having a, 64bit/32bit (and 128bit/64bit) pattern really. So this
is both a middle-end issue and a target issue.

Note there might be another bug asking for the same optimization.

Also note x86_64 might be the only popular target which has this kind of div
instruction so this might not get any attention as it is also a small peephole
where most people don't use 128bit integers either (they are non-standard
even).

[Bug target/105521] missed optimization in modulo arithmetic

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2022-05-08
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |NEW

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
.

[Bug target/105521] missed optimization in modulo arithmetic

[pinskia at gcc dot gnu.org]

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

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

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

[Bug target/105521] missed optimization in modulo arithmetic

[goswin-v-b at web dot de]

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

--- Comment #3 from Goswin von Brederlow <goswin-v-b at web dot de> ---
(In reply to Andrew Pinski from comment #1)
> This requires having a, 64bit/32bit (and 128bit/64bit) pattern really. So
> this is both a middle-end issue and a target issue.
> 
> Note there might be another bug asking for the same optimization.
> 
> Also note x86_64 might be the only popular target which has this kind of div
> instruction so this might not get any attention as it is also a small
> peephole where most people don't use 128bit integers either (they are
> non-standard even).

I know m68k had a 64bit/32bit pattern but it is indeed rare.

On x86_64 a (32bit * 32bit = 64bit) % 32bit uses the 128bit/64bit DIV
instruction and two extra truncation to 32bit for the input registers. On many
cpus that is significantly (factor 3-10) slower than the 64bit/32bit version.

This could potentially affect every / and % operation and preceding *, allowing
for the faster opcodes with fewer bits to be used where the compiler can reason
about the magnitude of the arguments.