Integer Multiply/Divide on Sparc

[John Whitmore]

In article <15418 at vlsisj.VLSI.COM> davidc at vlsisj.UUCP (David Chapman) writes:
>In article <84768 at linus.UUCP> bs at linus.mitre.org (Robert D. Silverman) writes:
>>Does any have, of know of software for the SPARC [SUN-4] that will
>>perform the following:
>>
>> [standard multiply and divide]
> . . .
>There should be instructions on the order of "multiply step" and "divide 
>step", each of which will do one of the 32 adds/subtracts and then shift.  
>
	I strongly disagree.  Smarter routines can optimize a lot of 
that kind of "microcode" away, and should do so given the opportunity.

>Thus they provide you with the tools to do your own multiply and divide.  
>One of the benefits is that a compiler can optimize small multiplies and 
>divides to make them execute quicker (i.e. multiply by 10 takes 4 steps 
>instead of 32).
	Yes, EXACTLY.  So extend the principle; take four-bit nibbles
of the argument and do a 16-way JUMP (whatever the equivalent is
on a SPARC) to sixteen cases like
CASE x0000:	RTN
CASE x0001:	add (to accumulator)
CASE x0010:	shift +1, add
CASE x0011:	subtract, shift+3, add
CASE x0100:	shift+3, add
CASE x0101:	add, shift+3, add
CASE x0110:	shift+2, add, shift+3, add
CASE x0111:	subtract, shift+4, add
	and if I can figure it out, you experts are getting bored
by now.  Four operations MAX for a four-bit multiplicand, opposed
to 12 operations (estimated) for the one-bit "MULSTEP" approach.
>
>P.S.  Don't write a loop on the order of "MULSTEP, DEC, BNZ" or it will be
>      incredibly slow.  Unroll the loop 4 or 8 times (MULSTEP, MULSTEP,
>      MULSTEP, MULSTEP, SUB 4, BNZ).  Branches are expensive.

	Hm.  The principle is good, but don't think small.  Unroll it
to really large chunks of code.  The "BNZ" is a bottleneck that
shouldn't be employed when really large fanout of the code path
can be done in ONE step.
	I seem to recall that the trick (above) was employed by a
hardware multiplier IBM made, some decade or more ago.  It still works.

I am known for my brilliance,                 John Whitmore
 by those who do not know me well.