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:
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.