Multiply Without a Multiply Instruction

The PA-RISC designers attacked this problem in the same way that we often attack performance problems with database applications. They did a frequency analysis of actual multiplications in real user programs. They found that 91 percent of multiply tasks use a constant operand which is known at compile time, that the constants tend to be small, that non-constant operands also tend to be small, and that 32-bit results occur more frequently than 64-bit results. They set out to optimize the frequent cases, even at the expense of the less frequent cases.

Any multiply can be converted into a series of additions and smaller multiplies. For example, 10 times x is the same as (5 times x) times 2, or even (4 times x plus x) times 2. The only tricky step is the last.

   120 = 10 x 12
   120 = (5 x 12) + (5 x 12)
   120 = ((4 x 12) + 12) + ((4 x 12) + 12)

The Shift-and-Add machine instructions multiply any register by 2, 4 or 8 and add to any register in one cycle. To multiply register x by 10 uses just two instructions:

Text version.

SH2ADD x,x,x;	shift x 2 bits (multiply by 4), add to x, store in x
ADD x,x,x;	add register x to itself and store in x

The compilers can convert any multiplication by a constant into a series of specific Add and Shift-and-Add instructions. PA-RISC can do such a multiply in four or fewer instructions, often in only two. When neither of the operands is known at compile-time, you have multiply-by-variable. Again the PA-RISC designers did frequency analysis and came up with a subroutine that includes optimizations for those special cases that occur most frequently.