Re: how to generate x86 "narrowing" divide instruction

Re: how to generate x86 "narrowing" divide instruction

[Jay Foad]

On 7 March 2011 18:32, Ian Lance Taylor <iant@google.com> wrote:
>> $ cat rand.c
>> #include <stdint.h>
>> uint32_t rand(uint32_t x) { return (uint64_t)x * 16807 % 0x7FFFFFFF; }

> The div instruction is difficult for gcc to use for 64->32 division
> because it generates an exception if the quotient is too large.  For
> code like the above gcc would have to insert runtime checks to make sure
> that the division did not overflow, even though the code only cares
> about the remainder.

I should have said explicitly: the division above can't overflow,
because the dividend can't be bigger than about 2^31 * 16807 (in
absolute value), so the quotient won't be bigger than about 16807. I
was hoping that value range propagation could work that out, so that
the compiler would know it's safe to use div.

Thanks,
Jay.

Re: how to generate x86 "narrowing" divide instruction

[Ian Lance Taylor]

Jay Foad <jay.foad@gmail.com> writes:

> On 7 March 2011 18:32, Ian Lance Taylor <iant@google.com> wrote:
>>> $ cat rand.c
>>> #include <stdint.h>
>>> uint32_t rand(uint32_t x) { return (uint64_t)x * 16807 % 0x7FFFFFFF; }
>
>> The div instruction is difficult for gcc to use for 64->32 division
>> because it generates an exception if the quotient is too large.  For
>> code like the above gcc would have to insert runtime checks to make sure
>> that the division did not overflow, even though the code only cares
>> about the remainder.
>
> I should have said explicitly: the division above can't overflow,
> because the dividend can't be bigger than about 2^31 * 16807 (in
> absolute value), so the quotient won't be bigger than about 16807. I
> was hoping that value range propagation could work that out, so that
> the compiler would know it's safe to use div.

It's a reasonable point.  Viewed that way one could call it a phase
ordering problem.  The knowledge that the range of the value is limited
is long gone by the time it comes to code generation.  And gcc never
generates div for 64->32 anyhow, because that knowledge is long gone.  I
would still describe this as a missed optimization.  It's fixable.  It's
a highly processor specific optimization, applicable to relatively few
programs, which has not been implemented.

Ian