9

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

11

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.

7
  • Carry is pretty obvious because the simplest logic element implementing an accumulator, the half adder, already produces it. The others are just combinations of bits entering and leaving the uppermost bit.
    – tofro
    Apr 28 '18 at 6:01
  • @tofro: I think the important step that instead of just producing a carry, storing it in a flag-register was what already has been accomplished (and that's also not hard, because you have to do something with the carry output, once you go beyond a bit-serial implementation where you just feed it back). The other flags are just extending that principle.
    – dirkt
    Apr 28 '18 at 6:11
  • 1
    @dirkt Overflow detection in the same manner is known since System/360 or earlier. It exposed overflow as CC=3 for arithmetic instructions, and carry as CC[1]=1 for logical (i.e. unsigned) instructions.
    – Netch
    Apr 29 '18 at 6:35
  • 2
    @Netch: I didn't say it's new, or happened at this particular stage. I said the logic how to do overflow detection in two's complement isn't obvious (at least to me). While pretty much all of the rest is.
    – dirkt
    Apr 29 '18 at 10:52
  • 2
    @rackandboneman: As the question states, prior designs didn't do it that way, so it's certainly not a byproduct of the hardware design; it's a design choice.
    – dirkt
    May 3 '18 at 4:02
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.

0

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.

9
  • Interesting - why 10 branches when it's only about 4 flags? Feels like there is some bloat, doesn't it? Also, where is carry handling?
    – Raffzahn
    Nov 22 at 2:34
  • 1
    Well, it's 14 branches (I missed some of the single-flag cases out because obviious, now added). 15 if you include BR, branch unconditional. Doesn't feel bloated to me, they're all useful. The 'unsigned' comparisons are especially useful for addresses. Nov 22 at 3:15
  • Note that sequences such as CMP A,B ; BGT FOO (which is implemented as a subtraction that discards the result) will give a correct decision even if there was overflow in the subtraction. Nov 22 at 3:24
  • Bloated in the sense that it needs only 8 branch instructions to test 4 flags (well technically 4 branches would do it), as with these 4 any useful combination can be synthesized. After all, flags are the way to get rid of byzantine conditional instructions (e..g. 7030 :))
    – Raffzahn
    Nov 22 at 12:25
  • And then you're having to code multiple branches, or even branches around branches, to get, for example, the effect of the very common BGT. Nov 22 at 12:44

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.