[Bug c/14224] New: GCC generates bad assembly for integer division

[terpstra at ito dot tu-darmstadt dot de]

When dividing a 64 bit integer by a 32 bit integer (normal division or
remainder), gcc uses __umoddi3 even though the intel instruction 'div' can do
this natively.

On my machine, this bad assembly has a speed impact of at least 1.5* by simply
replacing the call with 'div' and no further optimizations applied.

These types of operations (multiplication and then modulus division) are very
common in cryptography and coding theory. It is quite possible that fixing this
bug would greatly improve gcc's performance in these areas.

I have confirmed that this bug applies to versions 3.5, 3.4, and 2.95.4 in
addition to the 3.3.3 against which it is filed.

The example program is:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
 
int main(int argc, char** argv)
{
        int i = 0;
        uint32_t x = atol(argv[1]), y = atol(argv[2]), z = 0;
         
        for (i = 0; i < 1000000000; ++i)
        {
                z += ((uint64_t)x*(uint64_t)y) % 3221225473UL;
                ++x; ++y;
        }
         
        printf("%d\n", z);
         
        return 0;
}

Compile with gcc -O2 foo.c -o foo (version 3.3.3).
Then generate the assembly gcc -O2 foo.c -o foo.s and apply this patch:

47,54c47,64
<       movl    %eax, (%esp)
<       xorl    %eax, %eax
<       movl    %edx, 4(%esp)
<       movl    $-1073741823, %edx
<       movl    %edx, 8(%esp)
<       movl    %eax, 12(%esp)
<       call    __umoddi3
<       addl    %eax, -16(%ebp)
---
>
> // stuff from gcc:
> //    movl    %eax, (%esp)
> //    xorl    %eax, %eax
> //    movl    %edx, 4(%esp)
> //    movl    $-1073741823, %edx
> //    movl    %edx, 8(%esp)
> //    movl    %eax, 12(%esp)
> //    call    __umoddi3
> //    addl    %eax, -16(%ebp)
>
> // my custom assembly:
>       movl    $-1073741823, %ecx
>       div     %ecx
>       addl    %edx, -16(%ebp)
>
> // --- end changes
>

Now compile the assembly (gcc foo.s -o foo2) and compare the results and the
speed difference. It is quite likely that gcc could do an even better job
through good pipelining and better register assignment. Furthermore, in this
particular example code, the divisor is a constant which might allow gcc to even
optimize away the div altogether. However, I have no idea what the performance
impact of this would be.

-- 
           Summary: GCC generates bad assembly for integer division
           Product: gcc
           Version: 3.3.3
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: terpstra at ito dot tu-darmstadt dot de
                CC: gcc-bugs at gcc dot gnu dot org
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14224