[Bug c/102014] New: [missed optimization] __uint128_t % uint64_t emits a call to __umodti3 instead of div instruction

[Bug c/102014] New: [missed optimization] __uint128_t % uint64_t emits a call to __umodti3 instead of div instruction

[kamkaz at windowslive dot com]

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

            Bug ID: 102014
           Summary: [missed optimization] __uint128_t % uint64_t emits a
                    call to __umodti3 instead of div instruction
           Product: gcc
           Version: 11.2.1
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: kamkaz at windowslive dot com
  Target Milestone: ---

The following code:

    #include <stdint.h>
    extern u64 safe_mul(uint64_t a, uint64_t b, uint64_t n) {
        return (((__uint128_t)a)*b)%n;
    }

compiled with -O2 for x86_64 architecture generates following assembly:

    safe_mul(unsigned long, unsigned long, unsigned long):
        mov     rax, rdi
        mov     r8, rdx
        sub     rsp, 8
        xor     ecx, ecx
        mul     rsi
        mov     rsi, rdx
        mov     rdi, rax
        mov     rdx, r8
        call    __umodti3
        add     rsp, 8
        ret

With call to __umodti3, while it could compiled to:

    safe_mul(unsigned long, unsigned long, unsigned long):
        mov     rax, rdx
        mul     rcx
        div     r8
        mov     rax, rdx
        ret

The same thing happens with division __uint128_t / uint64_t and unnecessary
call to __udivti3 instead of div instruction.

[Bug c/102014] [missed optimization] __uint128_t % uint64_t emits a call to __umodti3 instead of div instruction

[jakub at gcc dot gnu.org]

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

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> ---
No, that is not a safe optimization.  The x86 128-bit by 64-bit DIV instruction
will #DE if the quotient is larger than ~(uint64_t) 0, you won't get a modulo
in that case even when the modulo is guaranteed to be representable.
Consider e.g. a == b == 0x3fffffffffffffffULL and n == 3.

[Bug c/102014] [missed optimization] __uint128_t % uint64_t emits a call to __umodti3 instead of div instruction

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |DUPLICATE
             Status|UNCONFIRMED                 |RESOLVED

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

*** This bug has been marked as a duplicate of bug 58897 ***