GCC does integer division badly on i386

["Wesley W. Terpstra" <terpstra at ito dot tu-darmstadt dot de>]

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.

The compiler correctly noticed that two 32 bits ints promoted to 64 bit for
the purposes of multiplication can be done with a normal intel multiplication.

What the compiler didn't seem to notice is that dividing a 64 bit integer by
a recently promoted 32 bit integer can use the normal intel div instruction.

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?

-- 
Wesley W. Terpstra