[Bug target/14224] GCC generates pessimizes code for integer division

[terpstra at ito dot tu-darmstadt dot de]

------- Additional Comments From terpstra at ito dot tu-darmstadt dot de  2004-04-05 14:57 -------
(In reply to comment #2)
> Problem here is, that maximum quotient should always be 2^32-1, as it should fit
> in 32bit EAX register. Consider the case, when dividend is 0x0000 0001 0000 0000
> and divisor is 0x0000 0001. The result won't fit in 32 bits, and division will
> produce #DE exception.
> 
> For your case, divisor is 0xC000 0001. And with your assembly, if x*y is equal
> or more than 0xC000 0001 0000 0000 (= 13835058059577131008), #DE exception will
> be generated.

You're quite right; I hadn't considered this.

> I suggest to mark this bug as invalid, because it is not possible for gcc to
> know maximum value of (x*y).

It's really a shame there's no way to inform gcc about the size.
For modulus arithmetic, x and y are known to be less than m.
Therefore, x*y%m and x*y/m must both fit in the registers.
                                                                                
However, I have a couple points to make still.
                                                                                
Firstly, the modulus will always fit inside EDX, regardless of the size of
the product. I'm not an assembler expert, but isn't it possible to turn off
the arithmetic exceptions prior to running DIV? As long as the code is only
interested in the modulus, this would be much faster.
                                                                                
At least in the case of finite mathematics (cryptography, coding theory,
etc) only the modulus really matters and computing it is often also the
critical section of the code.
                                                                                
Even if the code is interested in both the quotient and the modulus, it
seems that a quick comparison of the high 32bit part of EDX:EAX with the
modulus could determine whether or not a DIV would suffice. If it doesn't
then umoddi could be a fallback.

-- 


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