Re: GCC does integer division badly on i386

["Zack Weinberg" <zack at codesourcery dot com>]

"Wesley W. Terpstra" <terpstra@ito.tu-darmstadt.de> writes:

> Consider the following function:
>
> inline uint32_t field_mul(uint32_t x, uint32_t y)
> {
>         return ((uint64_t)x * (uint64_t)y) % 3221225473UL; // 3*2^30+1
> }
>
> GCC 3.3.3 compiles this to: (using -O2)
> field_mul:
>         pushl   %ebp
>         movl    $-1073741823, %ecx
>         movl    %esp, %ebp
>         subl    $24, %esp
>         movl    12(%ebp), %eax
>         mull    8(%ebp)
>         movl    %ecx, 8(%esp)
>         xorl    %ecx, %ecx
>         movl    %ecx, 12(%esp)
>         movl    %eax, (%esp)
>         movl    %edx, 4(%esp)
>         call    __umoddi3
>         movl    %ebp, %esp
>         popl    %ebp
>         ret
>
> ... which gives the correct answer but is really stupid assembly.

3.4 and 3.5 generate

field_mul:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        pushl   $0
        movl    12(%ebp), %eax
        mull    8(%ebp)
        pushl   $-1073741823
        pushl   %edx
        pushl   %eax
        call    __umoddi3
        addl    $16, %esp
        leave
        ret

which is tighter but still contains the undesirable library call.

> In problem areas like cryptography and coding theory these operation are
> carried out many, many times. GCC getting this assembly wrong could be
> causing a serious performance loss. Not to mention, in the above code the
> modulus divisor is a constant, which might allow for a reduction to simpler
> operations still than a div instruction.
>
> Is this a GCC bug?

Yes.  Please file a bug report using bugzilla
(http://gcc.gnu.org/bugzilla/).  It would be helpful if you included
a hand-optimized assembly example as well as the source and the
assembly generated by the compiler.  This is probably a simple fix.

zw