public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug c/14224] New: GCC generates bad assembly for integer division
@ 2004-02-20 11:38 terpstra at ito dot tu-darmstadt dot de
  2004-02-20 16:23 ` [Bug target/14224] GCC generates pessimizes code " pinskia at gcc dot gnu dot org
                   ` (3 more replies)
  0 siblings, 4 replies; 6+ messages in thread
From: terpstra at ito dot tu-darmstadt dot de @ 2004-02-20 11:38 UTC (permalink / raw)
  To: gcc-bugs

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


^ permalink raw reply	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2021-06-08  8:59 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [not found] <bug-14224-4@http.gcc.gnu.org/bugzilla/>
2021-06-08  8:41 ` [Bug target/14224] GCC generates pessimizes code for integer division pinskia at gcc dot gnu.org
2021-06-08  8:59 ` jakub at gcc dot gnu.org
2004-02-20 11:38 [Bug c/14224] New: GCC generates bad assembly " terpstra at ito dot tu-darmstadt dot de
2004-02-20 16:23 ` [Bug target/14224] GCC generates pessimizes code " pinskia at gcc dot gnu dot org
2004-04-05 13:31 ` uros at kss-loka dot si
2004-04-05 14:58 ` terpstra at ito dot tu-darmstadt dot de
2004-06-03  3:56 ` pinskia at gcc dot gnu dot org

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).