Origin of the NZVC condition codes scheme?

Question

The NZVC condition codes scheme, and corresponding set of 14 conditions for branches, is almost the only one in current ISAs that utilizes condition codes at all. The first computer I know that used it is PDP-11 (1970).

Is PDP-11 the truly first for this?

How was this scheme invented? I failed to find similar prototypes in earlier computers, and it looks like it appeared "from scratch". The condition codes themselves in the Program Status Word register (or similar) were, of course, known for more than a decade, but no such elaborated scheme was present. This looks like a single genius strike. Are there any memories from DEC?

---

More details: for example, to compare with System/360:

Signed arithmetic instructions produce condition code:

• CC=0: no overflow, result == 0
• CC=1: no overflow, result > 0
• CC=2: no overflow, result < 0
• CC=3: overflow, result sign/zero are irrelevant, compared with the overflow fact

Unsigned ("logical") arithmetic instructions produce condition code:

• CC[0]: result is not zero
• CC[1]: carry out of result width

One should combine results of both types to a single condition code set, and this is the first part of the leap I mean. The second one is using carry flag in combined 3-argument ADC/SBC operations (S/360 haven't done this despite carry bit in CC).

Answer 1

My take is that this scheme has been invented the same way everything has been invented: Slowly, by evolution and combining existing ideas, and not "from scratch" by a strike of genius.

The carry flag has been around a long time before that (other PDPs, and previous computers). Branches or skips that test the carry flag have also been around (other PDPs, and previous computers). Branches or skips that combine testing the carry flag with testing the accumulator for the sign bit, or equality to zero have also been around.

From there it's only a small step to add extra flag bits for the sign and zero to the carry flag, especially if you are about to make a program status word anyway. And while you are at it, you can also add on overflow bit for signed 2's complement.

If anything, I'd consider the overflow bit for signed 2's complement a strike of genius, because that (and its implementation) isn't really obvious.

Answer 2

This looks like a single genius strike

Na, not really, they are essentially the flags that can come out of an ALU, or more correct, they are the outputs that can be brought directly out of an ALU.

Just imagine the idea is to separate instructions and branching to reduce instruction set size and improve reusability. Looking at an ALU with this goal in mind will directly lead to these flags.

So if at all, the genius is to do away with complex test-and-branch instructions and create a modular set of branches to be used independent from test/arithmetic/logic instructions.

How this scheme has been invented?

Two reasons:

1. separating ALU instructions and branching

2. simplifying logic to create less expensive machines.

These flags come right out of the ALU, so the most simple logic is to store them right away. Using a CC based logic, like the /360 does means they need to be converted into a (more compact) condition code.

---

Where did it Come From

Both approaches (Flags and CC) are a step away from branch instructions being part of computational operations - that is testing for implied operations, like the IBM 7030 did with its byzantine flood of branch instructions or the PDP-8 with its way smaller, but still entangled set (*1). Such instructions would perform a certain test - like if the accumulator is zero and branch within the same operation.

It might not seem big at first, after all, doing a Branch When Zero after an Addition feels like testing the accumulator for zero. But it isn't, it now tests a recorded result. Branches and condition yielding operations are now separate entities and can be combined in new ways. New operations that need to be tested, like I/O, do no longer need a separate set instructions with or without testing. Call it a step toward RISC if you like.

Essentially to approaches were to be taken:

• Using hardware related flags, or
• Using abstract conditions

Using Flags simplifies the separation of operation and related branch by using the ALU output as a logical layer of separation, while condition code goes a step further by freeing the branching from any fixed framework defined by ALU operation or whatever the source of the previous operation is.

Lets take a look at them in detail:

Using Flags

Advantages of Using Flags:

• Simple hardware
• Straight implementation
• No layer of abstraction to be performed
• One pair of branches per flag

Disadvantages of Using Flags:

• Weak abstraction layer
• Testing flags is testing hardware states, not logical conditions.
• Meaning logical ties to ALU operations
• Extensions will need their own flags
  • Or their meaning gets rather confusing (*2)
• Getting quite bloaty when extended or non ALU operations are added
• Each additional flag adds two more branch instructions

Using Condition Codes

Advantages of Using a Condition Code

• Abstraction layer between CC generation and CC usage
• Hardware independent meaning of the used codes
• Easy reuse for non ALU operations
• Only 8 (*3) branch variations needed to test them
• Using 16 branch variations (*4) allows to test arbitrary combinations (*5)
• Improving code density.

Disadvantages of Using Condition Codes

• Higher hardware effort for encoding and decoding

Conclusion

The use of flags on the PDP-11 offers the freedom of separation of branching from testing/computing, while needing the least hardware effort, while, just 4 flags, being still not far from the instruction set cost (*6) of using condition codes.

The important part here is to keep in mind that the PDP series was always about cost - the PDP-11 especially as being driven by the success of the DG Nova heavy cutting DEC's PDP-8 sales. And cost (in terms of needed gates) was again what drove (early) microprocessor development.

The rest is history.

---

*1 - Well, With the Link (Carry) bit the PDP-8 had already one of them as dedicated flag, as its value was as well needed for multi precision operations.

*2 - The Z80s implementation of Overflow being a nice example

*3 - The fact that a CC encoding needs only 8 branches to do the same where a flag encoding need 16 is simply due redundancies within flag encoding. For example an outcome can never be ZERO and NEGATIV at teh same time. CC encoding does not cover this, thus being more compact.

*4 - Like the /360 did.

*5 - For example ne branch can test for Zero or Negative at once. Doing the same for a 4 bit flag word requires 256 branches.

*6 - Number of instruction encoding needed.

Answer 3

If you're going to have a condition-codes register where each bit represents an independent state (as opposed to some enumerated value for all possible outcomes), then NZVC are the necessary flags.

Overflow - for checking the result of arithmetic operations.

Carry - for extended-precision integer arithmetic.

Zero - for branch on equal/not equal (the alternative being a combined test-and-branch that would, on the PDP-11, have to handle all addressing modes).

Negative - for branch on less-than/not less than.

The combination of these can handle all possibilities, so you end up with branch on comparisons or arithmetic results, as follows:

• less than, signed (BLT, N^V == 1)
• less than, unsigned (BCS or BLO, C == 1)
• less than or equal, signed (BLE, Z|(N^V) == 1)
• less than or equal, unsigned (BLOS, C|Z == 1)
• greater than or equal, signed (BGE, N^V == 0)
• greater than or equal unsigned (BCC or BHIS, C == 0)
• greater than, signed (BGT, Z|(N^V) == 0)
• greater than, unsigned (BHI, C|Z == 0)

as well as simple tests on the flags

• equal (BEQ, Z == 1)
• not equal (BNE, Z == 0)
• branch on overflow (BVS, V == 1)
• branch on not-overflow (BVC, V == 0)
• branch on carry (BCS or BLO, C == 1)
• branch on not-carry (BCC or BHIS, C == 0)
• branch on negative (BMI, N == 1)
• branch on positive (BPL, N == 0)

where | is inclusive-or, ^ is exclusive-or

Note that I wrote branch on [not] carry in both lists due to the dual role it served.

---

It might be useful to consider this case:

CMP #77777, #177777   ; compare 32767 to -1

This computes 77777 - 177777, resulting in 100000
The condition codes are Z=0, N=1, V=1, C=1

BGE is implemented as 'branch if N and V are the same', thus we branch. 32767 is indeed greater than or equal to -1. We absolutely need to take overflow into account. Checking only the sign of the result would incorrectly report that 32767 was less than -1 (so no branch).

On the S/360, per the description in the question, we'd set a condition of 3, which only tells us that overflow occurred. The result of the comparison is not known.