🚀 go-pugleaf

Lawrence Kirby <fred@genesis.demon.co.uk> writes:
>
> colin@nyx10.cs.du.edu "Colin Plumb" writes:
> >word32 mod31(word32 x)
> >{
> >  /* First, 5*4 = 20 bits, and add 1 to prevent 0 result */
> >  x = (x & 0xfffff) + (x >> 20) + 1;
> >  /* Then 10 bits */
> >  x = (x & 0x3ff) + (x >> 10);
> >  /* Then 5 bits */
> >  x = (x & 0x1f) + (x >> 5);      /* 1 <= Result <= 0x3f */
> >  /* Then fold back in any overflow and subtract the extra 1 */
> >  x = (x & 0x1f) + (x >> 5);      /* 1 <= Result <= 0x20 */
> >  x = (x & 0x1f) + (x >> 5) - 1;  /* 0 <= Result <= 0x1e */
> >}
>
> This replaces 1 division operation with, at a rough count, 17 'fast'
> operations. While this may be faster on many systems it would be unwise
> to assume it.

Humm, lemme put on my compiler hat, and rewrite this a bit, pretending
I'm on a dual-integer-issue machine that supports dependent adds
(which include some Sparcs & Alphas, probably HP & PowerPC as well):

t1  = x & 0xfffff
t2  = x >> 20        - Cycle 1
t3  = t1 + t2 + 1    - Cycle 2
t4  = t3 & 0x3ff
t5  = t3 >> 10       - Cycle 3
t6  = t4 + t5        - Cycle 4 (one instruction issued)
t7  = t6 & 0x1f
t8  = t6 >> 5        - Cycle 5
t9  = t7 + t8        - Cycle 6 (one instruction issued)
t10 = t9 & 0x1f
t11 = t9 >> 5        - Cycle 7
t12 = t10 + t11      - Cycle 8 (one instruction issued)
t13 = t12 & 0x1f 
t14 = t12 >> 5       - Cycle 9
t15 = t13 + t14 - 1  - Cycle 10

Quad issue boxes probably can't do this much faster due to
dependencies.  However, 10 clocks beats integer divide on many
machines. 

Cliff

--
Cliff Click                  Compiler Researcher & Designer
RISC Software, Motorola      PowerPC Compilers
cliffc@risc.sps.mot.com      (512) 891-7240