31

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?

chicks
  • 397
  • 1
  • 4
  • 15
Omar and Lorraine
  • 38,883
  • 14
  • 134
  • 274
  • 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 '22 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 '22 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 '22 at 17:18
  • IOW, the market was different, the price point was different, and thus, the engineering trade-offs were different. Plus few of the -6s were actually sold: Wikipedia says <25. So ... those extra instructions weren't really that much of a draw ... – davidbak May 26 '22 at 17:22
  • I might be wrong, but wasn't the PDP-11 (like he Nova) build around the 74181? BIC is one of it's operation - and quite handy masking not set bits. In addition, if at all, the influence was on the 6800 instruction set, as the 6800, which included BIT - in turn inherited by the 6500 – Raffzahn May 26 '22 at 18:59
  • @Raffzahn - but that page shows the 74181 has all the other interesting operations the OP is asking about - the -11 designers could have chosen practically any set of primitives out of the '181 had they wished ... so why these? (Assuming it was built of '181s.) – davidbak May 26 '22 at 19:51
  • @davidbak That's why I didn't write an answer, it would be pure speculation, as there are, as you mention, other interesting choices. Just, there wasn't enough coding room for all '181 operations (also some are rather exotic), so they had to select what's most useful. BIT and BIS are easy choices and BIC is, as mentioned, great for masking, complementing BIT. Comment was meant as hint about what choices they have had to select from. – Raffzahn May 26 '22 at 20:00
  • @davidbak You're right — maybe the -7 or -9 would have been fairer comparisons. These I believe have the instructions I wish the -11 did. Do you think the 68k is a fair comparison? – Omar and Lorraine May 26 '22 at 21:12
  • 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. – dave May 27 '22 at 01:00
  • Compare -11 to -8, not -6. Then the progress would be obvious. Also I think -11 could be much better if they'd choose 1.5-address instructions and not 2-address, like 68k later did -- while also inheriting much from -11. – lvd May 27 '22 at 06:06
  • @davidbak: as stated PDP-6 was quickly superseded by -10 with same ISA, which lasted decades and sold thousands (many to sites important on ARPAnet and early Internet) -- though decidely not the half-million of the -11. – dave_thompson_085 May 27 '22 at 08:46
  • @dave_thompson_085 - oh sure, the -10 is my favorite ISA ever - I was just making a joke about "not really that much of a draw" if that's what you're referring to. – davidbak May 27 '22 at 19:22
  • @davidbak less than 25 sold? That's still almost five times the once estimated global need for computers – Hagen von Eitzen May 28 '22 at 09:03
  • I would suggest that the PDP-6 solution is a way of sidestepping the design issue rather than grappling with it. If you are willing to expend one eighth of your opcode space to implement 64 Boolean instructions, some of which are no-ops or nonsensical, you can use 4 bits from the opcode field as a truth table, and implement 16 boolean operations with almost no logic. The PDP-11 designers were much more interested in choosing a useful subset of boolean operators, in order to avoid wasting opcode space. – Walter Mitty May 29 '22 at 11:18
  • I would rate the lifespan of the PDP-10 from 1968, when the KA-10 was built, to 1983, when the Jupiter project was cancelled. To be sure, there were lots of PDp-10s still running in the 1990s, but the product was no longer the flagship for DEC. – Walter Mitty May 29 '22 at 13:20
  • I'm confused. If there are "four bits to specify the opcode", then how is the bitfield used to specify the opcode only three bits wide? If three bits are used, and 000 and 111 are reserved (leaving six possible values), how are seven opcodes represented? – Karl Knechtel May 29 '22 at 18:13
  • 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. – Omar and Lorraine May 30 '22 at 09:15

4 Answers4

45

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.

dirkt
  • 27,321
  • 3
  • 72
  • 113
  • 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. – dave May 28 '22 at 16:57
26

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.

davidbak
  • 6,269
  • 1
  • 28
  • 34
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 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.

Omar and Lorraine
  • 38,883
  • 14
  • 134
  • 274
supercat
  • 35,993
  • 3
  • 63
  • 159
1

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.

Omar and Lorraine
  • 38,883
  • 14
  • 134
  • 274
PDP11
  • 718
  • 2
  • 12
  • However, I think the question was really "why these particular ops rather than others". My take (as an actual PDP-11 programmer) is that the provided ops map directly to what I most want to do: set bits, clear bits, test whether bits are set. 'Setting bits' is a logical-or, sure, but I'm still thinking in terms of setting bits (in a status register, for example). And I think of 'clearing bits', not 'anding with the complement of the bits I want to clear'. – dave Aug 08 '22 at 16:20
  • I would refer to: https://gordonbell.azurewebsites.net/CGB%20Files/New%20Architecture%20PDP11%20SJCC%201970%20c.pdf – PDP11 Aug 08 '22 at 20:05
  • For the "why these particular ops rather than others" I would refer to: https://gordonbell.azurewebsites.net/CGB%20Files/New%20Architecture%20PDP11%20SJCC%201970%20c.pdf http://gordonbell.azurewebsites.net/cgb%20files/what%20have%20we%20learned%20from%20the%20pdp-11%201977%20c.pdf http://bitsavers.org/pdf/dec/_Books/Bell-ComputerEngineering.pdf – PDP11 Aug 08 '22 at 20:44
  • Offhand, I'd say the first ref supports my pragmatic viewpoint - "Since a common use of a byte is to hold several flag bits (booleans)". I hadn't noticed before that BIS is ⊃ though. – dave Aug 08 '22 at 20:49
  • Good links! For some reason I never thought to look for Gordon Bell's own website ... – davidbak Aug 09 '22 at 03:40