8

Before integer multipliers in silicon, several cpus had some support for multiplication. For instance SPARCv7 has the MULScc multiply-step instruction (several other cpus also have this).

As far as I know, PA-RISC computers before PA-7100 (probably) had no hardware for integer multiplication, but support for multiplication with a constant was enhanced beyond the usual shift and add instructions. Multiplication by a constant could be given by a sequence of instructions add, sub, sl, sh1add, sh2add, sh3add, neg and shl, see https://patents.google.com/patent/US5764990A/en

Were there other cpus, earlier or later, that used the strategy of PA-RISC (sh1add, sh2add, sh3add)?

7
  • 1
    Interesting they actually got a patent for that. This method has been around for decades before 1996 (Obviously not directly in the ALU, but by the appropriate series of separate instructions). And even if your CPU has multiply, shift+add might still be faster for some values than a generic multiplication
    – tofro
    Oct 9, 2018 at 17:07
  • 4
    Interestingly this (x<<a)+y kind of instructions has a lot of usage in address generation and pointer arithmetic, e.g. to increment y pointer by x integers. Oct 9, 2018 at 17:07
  • 2
    It's unclear to me whether combining shift and add into a single instruction really counts as "instruction set support" for multiplication by a constant. On the surface the sh1add, sh2add and sh3add instructions appear to be shortened opcodes that allow the address of 2-byte, 4-byte and 8-byte array entries to be computed in one step. The ability to leverage these array-lookup opcodes to multiply by arbitrary constants appears to be more of a compiler innovation than an instruction set one, and the patent is very clear that it is a method for compilers to use.
    – Ken Gober
    Oct 9, 2018 at 17:15
  • 3
    Isn’t that similar to the common x86 technique using LEA? Oct 9, 2018 at 17:18
  • @KenGober, there are more to the sh<x>add instructions than my abbreviated description. Yes, the patent deals with the way to store sequences, hence a compiler invention, but the underlying hardware enables such sequences in the first place.
    – Baard
    Oct 9, 2018 at 17:33

2 Answers 2

9

In the original ARM instruction set there are no dedicated shift and roll instructions; instead the second operand of each instruction always passes through the barrel shifter, so shifts and rolls are always applied as prefixes to other operations.

You can make the instruction a simple MOV to get the same result as a traditional shift or rotate operation.

Or you could make the instruction an ADD to get the same functionality as any of the listed sh?adds, or equivalents that shift or roll by any other amount in either direction.

I guess in a literal sense that's not the processor seeking to implement the same strategy as PA-RISC, it's a natural outcome of allowing rolls and shifts everywhere, but it gives the programmer the tools necessary to reach exactly the same outcome.

Design of the ARM began in 1983, it was first fabricated in 1985 and was on sale to the public within the ARM evaluation kit second processor for the BBC Micro either that year or in 1986 — the sources I found seemed to disagree. So it's at worst a simultaneous implementation to the PA-RISC; ARM's inclusion of both SUB and RSB (reverse subtraction, which switches the order of the operands) suggests that making sure the shifter could be used for the argument on either side of a subtraction was something that the designers realised would be useful.

1
  • 1
    For completeness, I'd also mention the year of introduction for ARM (1983) and PA-RISC (1986).
    – dirkt
    Oct 9, 2018 at 20:29
6

The VAX, sold first in 1977, has a scaled indexed addressing mode, which offers indexReg*constScale+baseReg address computation.  When used with an LEA instruction (load effective address), this offers a shift and add.

The 68020 (released 1984) introduced scaled indexed addressing mode, which when accomplishes indexReg*constScale + constOffset + baseReg; the 680x0 series also has LEA.

And one comment mentioned LEA on x86; the 80386, introduced 1985, supports a scaled indexed addressing mode as well.

You noted PA-RISC already, which was first released in 1986.

1
  • Scaled indexed addressing modes has often been pressed into service for constant multiplication. The way I stated the question this answer is good. However, the answer of @Tommy below is even better.
    – Baard
    Oct 9, 2018 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .