[PATCH] Improve integer division on IA-64

[Roger Sayle]

Hi Richard,

On Thu, 22 Dec 2005, Richard Henderson wrote:
> Sometime last year I played with division routines on Alpha,
> and used an LD_PRELOAD library to force the entire system to
> log every division operation for a couple of days.
>
> Unfortunately, I no longer have the raw data, but I remember
> that x [%/] 10 and x % pow2 were the only special cases worth
> looking at.  The former, x/10, made up like a third of all
> division operations.


Many thanks for your instrumentation code.  I've ported it to
ia64, compiled several OpenEye applications, cc1 and small
benchmarks (such as whetstone) with -shared-libgcc, and used
LD_PRELOAD to gather statistics.

Interestingly, the distributions I generate appear to contradict
your alpha findings that x/10 is extremely common.  From my testing
__udivdi by 32 is by far the most common operation in my workload,
and divisions by 10 are rarer than divisions by 72!

I'll admit that I found this surprising especially as the workload
did a signicant amount of printing of decimal numbers.  Digging
deeper, the answer is found in glibc's stdio-common/_itoa.h where
it turns out that %d and friends special case base 10, 8 and 16,
so the appropriate divisions and remainders are special cased
compile-time constants, and therefore use GCC's synth_mult sequences.

It's possible that your alpha investigations were on Tru64 that
didn't have this optimization, or an implementation on libc that
didn't optimize the common case of base 10, or used a compiler
that didn't prefer a synthetic sequence for x/10 and x%10, or
perhaps your analysis was biased by some other application that
internally did a lot of itoa, but was less optimized than glibc.


Roger
--