What motivated the weird boolean instruction repertoire of the PDP-11?

Question

The PDP-11 has seven dyadic instructions (I'm not counting the byte/word varieties separately), which take a full six bits for each of its operands. That's twelve bits to specify the operands, and four bits to specify the opcode.

These instructions are,

• add
• sub
• bit (computes a & b, discards the result and updates the flags only)
• bis (this should have been called or, since that's what it is)
• bic (computes a &= !b)
• cmp
• mov

The opcode space is quite crowded because the bitfield to specify the opcode is very narrow (only three bits!) and because two values for this bitfield are reserved (000 means the instruction is not dyadic, 111 is apparently reserved for later expansion).

I'm quite surprised by the lack of basics here. Beside byte-sized add and subtraction, I would expect at least an and, and an exclusive or. Maybe an add-with-carry instruction. It seems like a step back from the PDP-6 of six years earlier. I appreciate what I'm asking for can be synthesized from what's there, but that's at quite a cost, because of the Extremely Spacious way of specifying operands. For this reason I expect code density for PDP-11 programs to be quite low.

Around nine years after the first PDP-11, the apparently PDP-11 inspired 68000 from Motorola has the and and eor, but not bic or bit as far as I can see (the btst and bclr might make reasonable substitutes in some circumstances).

On the other hand, the PDP-11 seems to come out well in this paper concerning code density of various architectures. But that paper appears to consider the /40, which has at least an xor instruction from the wishlist up there.

Recap:

The PDP-11 needs a full six bits per operand, which is almost a byte. This puts pressure on the opcode space, meaning it can't possibly offer all the same instructions as, say, the PDP-6 did. But what they left out seems like the best instructions. This leaves the PDP-11 with a weird set of boolean instructions, quite unlike the repertoire offered by competitors/successors/predecessors. You'd expect this to mean that common operations need to be synthesized from what the PDP-11 offers. Yet, the PDP-11 compares favorably on code-density comparisons.

What am I missing?

Answer 1

I'm not sure what motivated this instruction selection, beyond that it is sufficient, but you may be overestimating the pessimization caused by not having the full repertoire of Boolean instructions.

Manually coding bit operations may have left the programmer frustrated by not having a more extensive instruction repertoire - and there were plenty of programmers coding the PDP-11 in assembler - but it was also an age of rapidly progressing compiler research and development (and the ubiquity of Digital computers in schools contributed to this in no small way!) - and to a compiler it's just another thing to toss into the mix.

I'll refer you to the discussion of the bittest(node, bit, label) code generation function and also the discussion of Generating Boolean Operations from one of my favorite books of the era: "The Design Of An Optimizing Compiler" (Wulf, Johnsson, Weinstock, Hobbs, Geschle) (Elsevier, 1975)¹ - describing the BLISS-11 compiler (cross-compiler, actually, it ran on a -10).

(Because for some reason Google Books didn't scan this book I've included my own studio-quality² photos of the relevant discussion - but you can also download the book from CMU's site here.)

The takeaway from the discussion of bittest is: Even with a dedicated instruction to test a bit there are special cases where you can generate even better code! (An assembly programmer might have known (some of) these cases and used them, but a compiler can identify them and apply them every time they're applicable.)

The takeaway from the discussion of "generating Boolean operations" is: yes, the PDP-11 is missing AND which is a pity, but in fact, many times (IMO: perhaps most of the time) the need for Boolean expressions is not for the expression itself, but in combination with other things you're doing at the same time, like extracting/shifting/inserting bitfields for example, and so you (i.e., the compiler) need to consider the overall source-level construct you're generating code for and not get so focused on individual sub-operations.

Plus, even when considering just a Boolean expression - it may be that the optimal thing to compute is actually the complement, or even some other expression that you can get to through Boolean algebra (de Morgan's law, etc. etc.). (IOW, maybe you see an AND in the source but you'd really do better by generating an OR ...)

Oh, and one more thing: The assembly programmer isn't left in the dust by any means. There are things a sufficiently clever (and desperate!) assembly programmer can do that even today's optimizing compilers can only dream of: arrange data structures - including fields within words but also the overall structure - so that certain arithmetic and Boolean operations can be done by instruction addressing modes! (Such as using the index register, or auto-{in|dec}crement, just to name two ideas.) And the PDP-11 did have some pretty cool addressing modes for its time!

Discussion of bittest:

Most of the discussion of "generating boolean expressions":

---

¹ Wikipedia says published in 1980 but this is wrong: my copy clearly shows 1975.

² Heh, just a joke. I know people on SE don't like jokes to interfere with their serious work, but IDC. Also it's my way of apologizing for the amateur quality of these photos.

Answer 2

What am I missing?

You are missing that in really the majority of real-world cases, and, or and not are used for bitmasks. And you need bitmasks all the time, in particular if you don't have that much memory as on the PDP-11, and you need to compress your data structures.

Looking at the names of the operations should also have given you a clue:

• bit = bit test (clobbers one register in other ISA's)
• bis = bit set (and that's why it's called this way, and not or)
• bic = bit clear (which needs two operations in other ISA's).

In conditions, and and or are implemented by using the right branch targets and branch conditions (and not with boolean opcodes).

So the majority of real-world code at that time would have benefitted from that ISA and it would have allowed denser code. It does come at the expense of the more rare cases when you actually need to do boolean operations in parallel on all bits of a register. Which happens for example in bitmap graphics (where xor is also very useful), but the PDP-11 didn't really use bitmap graphics.

You'd expect this to mean that common operations need to be synthesized from what the PDP-11 offers.

It's actually the other way round, in other ISA's bitfield operations need to be synthesized from and, or, and xor.

Answer 3

The functions AND and BIC together provide a means of partitioning the bits of a byte into two sets: those that match a mask and those that don't. Some instruction sets usefully include both (and IMHO more should), but programming languages more often include just "and" (even though IMHO they too should include both) and many instruction sets mirror that choice. If e.g. C used ~& to represent BIC, then a construct like u64value ~&= u32value; would promote the non-inverted right-hand argument, unlike u64value &= ~u32value; which would perform the inversion and then zero-extend the inverted value.

As for whether BIC or AND is more efficient as a machine instruction, I'd guess that in the absence of a BIT instruction, the most common use of AND/BIC would be to test whether any bits were set in both of the operands; the AND operation would be more useful than BIC in that case. On the other hand, in uses of AND/BIC where the individual bits of the result will be used, I think BIC is probably nicer.

Consider, for example, a graphics library that has an active pixel, and has operations to move up, down, left, or right, and to set or clear the current pixel. Moving up or down simply requires adjusting the offset by a row. Moving left or right involves rotating the current mask left or right and then adjusting the current address plus or minus a word if there's a carry. Setting or clearing a pixel could be done with BIS/OR and BIC if both are available, but on platforms that have AND instead it would be necessary to invert the mask before using AND.

I'm not sure how I'd judge the relative usefulness of BIC and XOR. That's a bit trickier, since BIC can be emulated by combining BIS and XOR, but synthesizing XOR is more expensive. While BIC is more commonly used, the absence of XOR in cases where it would be useful is a bigger hardship than would be the absence of BIC.

Answer 4

Recap:

The PDP-11 needs a full six bits per operand, which is almost a byte. This puts pressure on the opcode space, meaning it can't possibly offer all the same instructions as, say, the PDP-6 did. But what they left out seems like the best instructions. This leaves the PDP-11 with a weird set of boolean instructions, quite unlike the repertoire offered by competitors/successors/predecessors. You'd expect this to mean that common operations need to be synthesized from what the PDP-11 offers. Yet, the PDP-11 compares favorably on code-density comparisons.

What am I missing?

The constraints on the instruction set were actually determined by the limitations of the small and medium scale TTL technology available for the PDP-11/20. Design decisions regarding system cost and packaging determined CPU complexity. Instructions were decoded in hardware as microcode was not an option. ALUs such as the 74181 were not available so everything was implemented in SSI and MSI ICs. Refer to the PDP-11/20 Engineering drawings on Bitsavers http://www.bitsavers.org/pdf/dec/pdp11/1120/1120_SystemSchems_Feb70.pdf

Page 12 provides a block diagram Page 42 is the Instruction Decode board layout and Page 43 provides the instruction decode logic. Input from the Instruction Register is on the left with decoded instruction lines on the right.

With the available IC packaging technology in 1969 the system's instruction complexity was constrained. At the other end of the market in 1969 CDC released the Cyber 7600 supercomputer. What you have missed is the tradeoff in price/performance determined the instruction set complexity.