30

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?

17
  • 15
    If you intend to manipulate bits, you need a way to set bits (bis does that), clear bits (bic does that), and test whether bits are set (bit does that). Toggling bits is also helpful. Generalized bitwise and, or, and xor are theoretically useful, but in my experience 90+% of their use is for manipulating bits for the purpose I just described.
    – DrSheldon
    May 26 at 15:13
  • 4
    I feel your question in the title doesn't match the question you wind up asking in the body of your text. Are you asking why the PDP-11 designers made these choices? Or why the PDP-11's code density is favorable considering its opcode limitations?
    – Jim Nelson
    May 26 at 16:27
  • 2
    BTW, not sure why you're comparing an -11 to a -6. They're different beasts! The -6 was a large machine with a large price: $150K in 1965 and that was without RAM. (8KWords would set you back another $50K.) 4 years later the PDP-11 prices were ... different! - <$8K (with 128words - n.b: not 128Kwords!) and $7000 for 8Kwords of RAM. (Course, those were smaller words.) You'd expect a few more instructions for your $ in the -6!
    – davidbak
    May 26 at 17:18
  • 2
    Having worked as an -11 programmer for some years, I can say that I think the tradeoff between 'more instructions' and the actual arrangement of operand specifiers (register, mode, source and dest) was resolved in the best manner. Sure, it'd have been nice if the EIS instructions (XOR, MUL, DIV) would have fit the canonical 2-operand model, but hey, it was a mini. May 27 at 1:00
  • 1
    @KarlKnechtel, it's basically a three bit field for opcodes, adjacent to a one bit field to specify if it's 8-bit or 16-bits. Minus two reserved values, so that's 6 opcodes, each having two variants. But it's like they cut out 8-bit addition to put in 16-bit subtraction. I count those separately, so it adds up to seven.
    – OmarL
    May 30 at 9:15

3 Answers 3

24

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)1 - 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-quality2 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:

enter image description here

Most of the discussion of "generating boolean expressions":

enter image description here enter image description here enter image description here


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

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

43

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.

1
  • 2
    As far as I recall, most bit-twiddling that I did had a constant mask for the source, like BIS #ENAB,(R4) -- and think about device CSRs on the I/O page for examples. This extended to 'and' operations, where the inverse of the constant expression could usefully be computed by the assembler, like BIC ^C<A!B!C>,T.STS(R5) for clearing all but 3 bits in some status. In short, I agree with the proposition that BIS/BIC (and BIT) implemented the most useful cases. May 28 at 16:57
11

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.