🚀 go-pugleaf

In article <1255@otc.otca.oz> gregw@otc.UUCP (Greg Wilkins) writes:

>But what about multiplies by constants, the compiler will have turned these
>into wonderful sequences of shifts and adds.  If a mul instruction became
>available, these should be replaced by a load with constant followed by a
>multiply.  But then I guess nothing can solve this one (without greatly
>slowing the performance of all machines without a multiply instruction).

Converting I x C into a sequence of shifts, adds, and subtracts
is really a machine-dependent optimization -- it's not always
profitable.  In a short paper

	Multiplication by Integer Constants
	Robert Bernstein
	Software -- Practice and Experience, July 1986

Bernstein describes the method used by the PL.8 compiler to
handle 32x32 signed multiplies.  The cost of a multiply,
on an 801, using multiply-step instructions is 19 cycles.
The cost, using his scheme, is summarized below

	constant		# instructions
	---------------------------------------
	2			1
	3			2
	6			3
	11			4
	22			5
	43			6
	86			7
	171			8
	342			9
	683			10
	1366			11
	2731			12
	5462			13
	...

that is, multiplications by 2731 require 12 instructions.
Multiplications by C < 2731 require 11 or fewer instructions.
So, if you've got a multiplier that's quicker than 10 cycles,
you'd rather not convert some constants >= 683.

On the other hand, if you have lots of multiplies by
strange integer constants, converting them all
might expose opportunities for common subexpression
elimination.

Note that the above numbers are misleading for some machines.
If you don't have a barrel shifter or 3-address instructions or
adequate registers, the cost will be higher.

Preston Briggs
preston@titan.rice.edu