Why is there no `nand` instruction in modern CPUs?

Question

Why did x86 designers (or other CPU architectures as well) decide not to include it? It is a logic gate that can be used to build other logic gates, thus it is fast as a single instruction. Rather than chaining not and and instructions (both are created from nand), why no nand instruction?.

Answer 1

http://www.ibm.com/support/knowledgecenter/ssw_aix_61/com.ibm.aix.alangref/idalangref_nand_nd_instrs.htm : POWER has NAND.

But generally modern CPUs are built to match automated code generation by compilers, and bitwise NAND is very rarely called for. Bitwise AND and OR get used more often for manipulating bitfields in data structures. In fact, SSE has AND-NOT but not NAND.

Every instruction has a cost in the decode logic and consumes an opcode that could be used for something else. Especially in variable-length encodings like x86, you can run out of short opcodes and have to use longer ones, which potentially slows down all code.

Answer 2

The cost of such an ALU functions is

1) the logic that performs the function itself

2) the selector that selects this function result instead of the others out of all ALU functions

3) the cost of having this option in the instruction set (and not having some other usefull function)

I agree with you that the 1) cost is very small. The 2) and 3) cost however is almost independent of the function. I think in this case the 3) cost (the bits occupied in the instruction) were the reason not to have this specific instruction. Bits in an instruction are a very scarce resource for a CPU/architecture designer.

Answer 3

Turn it around - first see why Nand was popular in hardware logic design - it has several useful properties there. Then ask whether those properties still apply in a CPU instruction...

TL/DR - they don't, so there's no downside to using And, Or or Not instead.

The biggest advantage to hardwired Nand logic was speed, gained by reducing the number of logic levels (transistor stages) between a circuit's inputs and outputs. In a CPU, the clock speed is determined by the speed of much more complex operations like addition, so speeding up an AND operation won't enable you to increase clock rate.

And the number of times you need to combine other instructions is vanishingly small - enough so that Nand really doesn't earn its space in the instrucnion set.

Answer 4

I'd like to agree with Brian here, and Wouter and pjc50.

I'd also like to add that on general-purpose, especially CISC, processors, instructions don't all have the same throughputs – a complicated operation might simply take more cycles that an easy one.

Consider X86: AND (which is an "and" operation) is probably very fast. Same goes for NOT. Let's look at a bit of disassembly:

Input code:

#include <immintrin.h>
#include <stdint.h>

__m512i nand512(__m512i a, __m512i b){return ~(a&b);}
__m256i nand256(__m256i a, __m256i b){return ~(a&b);}
__m128i nand128(__m128i a, __m128i b){return ~(a&b);}
uint64_t nand64(uint64_t a, uint64_t b){return ~(a&b);}
uint32_t nand32(uint32_t a, uint32_t b){return ~(a&b);}
uint16_t nand16(uint16_t a, uint16_t b){return ~(a&b);}
uint8_t nand8(uint8_t a, uint8_t b){return ~(a&b);}

Command to produce assembly:

gcc -O3 -c -S  -mavx512f test.c

Output Assembly (shortened):

    .file   "test.c"
nand512:
.LFB4591:
    .cfi_startproc
    vpandq  %zmm1, %zmm0, %zmm0
    vpternlogd  $0xFF, %zmm1, %zmm1, %zmm1
    vpxorq  %zmm1, %zmm0, %zmm0
    ret
    .cfi_endproc
nand256:
.LFB4592:
    .cfi_startproc
    vpand   %ymm1, %ymm0, %ymm0
    vpcmpeqd    %ymm1, %ymm1, %ymm1
    vpxor   %ymm1, %ymm0, %ymm0
    ret
    .cfi_endproc
nand128:
.LFB4593:
    .cfi_startproc
    vpand   %xmm1, %xmm0, %xmm0
    vpcmpeqd    %xmm1, %xmm1, %xmm1
    vpxor   %xmm1, %xmm0, %xmm0
    ret
    .cfi_endproc
nand64:
.LFB4594:
    .cfi_startproc
    movq    %rdi, %rax
    andq    %rsi, %rax
    notq    %rax
    ret
    .cfi_endproc
nand32:
.LFB4595:
    .cfi_startproc
    movl    %edi, %eax
    andl    %esi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand16:
.LFB4596:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc
nand8:
.LFB4597:
    .cfi_startproc
    andl    %esi, %edi
    movl    %edi, %eax
    notl    %eax
    ret
    .cfi_endproc

As you can see, for the sub-64-sized data types, things are simply all handled as longs (hence the andl and notl), since that's the "native" bitwidth of my compiler, as it seems.

The fact that there's movs in between is only due to the fact that eax is the register that contains a function's return value. Normally, you'd just calculate on in the edi general purpose register to calculate on with the result.

For 64 bits, it's the same – just with "quad" (hence, trailing q) words, and rax/rsi instead of eax/edi.

It seems that for 128 bit operands and larger, Intel didn't care to implement a "not" operation; instead, the compiler produces an all-1 register (self-comparison of the register with itself, result stored in the register with the vdcmpeqd instruction), and xors that.

In short: By implementing a complicated operation with multiple elementary instructions, you don't necessarily slow down operation – there's simply no advantage to having one instruction that does the job of multiple instructions if it isn't faster.

Answer 5

First off don't confuse bitwise and logical operations.

Bitwise operations are usually used to set/clear/toggle/check bits in bitfields. None of these operations require nand ("and not", also known as "bit clear" is more useful).

Logical operations in most modern programming languages are evaluated using short-circuit logic. So usually a branch-based approach to implementing them is needed. Even when the compiler can determine that short-circuit vs. complete evaluation makes no difference to program behaviour, the operands for the logical operations are usually not in a convenient form to implement the expression using the bitwise asm operations.

Answer 6

NAND is often not implemented directly because having the AND instruction implicitly gives you the ability to jump on a NAND condition.

Performing a logical operation in a CPU often sets bits in a flag register.

Most flag registers have a ZERO flag. The zero flag is set if the result of a logical operation is zero, and cleared otherwise.

Most modern CPUs have a jump instruction that jumps if the zero flag is set. They also have an istruction that jumps if the zero flag is not set.

AND and NAND are complements. If the result of an AND operation is zero then the result of a NAND operation is 1, and vice versa.

So if you want ot jump if the NAND of two values is true then just perform the AND operation, and jump if the zero flag is set.

So if you want ot jump if the NAND of two values is false then just perform the AND operation, and jump if the zero flag is clear.

Answer 7

Just because something is cheap doesn't mean it's cost-effective.

If we take your argumentation ad absurdum, we'd reach conclusion that a CPU should be composed mostly of hundreds flavors of NOP instruction - because they are the cheapest to implement.

Or compare it to financial instruments: would you buy a $1 bond with 0.01% return just because you can? No, you'd rather save those dollars until you have enough to buy a $10 bond with better return. Same goes with silicone budget on a CPU: it's effective to ax many cheap but useless ops like NAND, and put the saved transistors into something way more expensive but genuinely useful.

There is no race to have as many ops as possible. As RISC vs CISC had proven what Turing knew from the very beginning: less is more. It's actually better to have as few ops as possible.

Answer 8

On a hardware level, either nand or nor is the elementary logic operation. Depending on the technology (or depending what you arbitrarily call 1 and what you call 0), either nand or nor can be implemented in a very simple, elementary way.

If we ignore the "nor" case, all other logic is constructed from nand. But not because there is some computer science proof that all logic operations can be constructed from and - the reason is that there just isn't any elementary method to build xor, or, and etc. that is better then constructing it from nand's.

For computer instructions, the situation is different. A nand instruction could be implemented, and it would be a tiny bit cheaper than implementing xor, for example. But only a tiny bit, because the logic that calculates the result is tiny compared to the logic that decodes the instruction, moves operands around, makes sure that one operation only is computed, and picks up the result and delivers it to the right place. Each instruction takes one cycle to execute, same as an addition which is ten times more complicated in terms of logic. The savings of nand vs. xor would be negligible.

What counts then is how many instructions are needed for operations that are actually performed by typical code. Nand is nowhere near the top of the list of commonly requested operations. It is much more common that and, or, not are requested. Processor and instruction set designers will examine lots of existing code and determine how different instructions would affect that code. They most likely found that adding a nand instruction would lead to very little reduction in the number of processor instructions executing to run typical code, and replacing some existing instruction with nand would increase the number of instruction performed.

Answer 9

Just because NAND (or NOR) can implement all gates in combinational logic, doesn't translate to an efficient bitwise operator in the same way. To implement an AND using just NAND operations, where c= a AND b, you'd have to have c=a NAND b, then b=-1, then c=c NAND b (for a NOT). The basic logic bitwise operations are AND, OR, EOR, NOT, NAND, and NEOR. That's not a lot to cover, and the first four are generally built in anyway. In combinational logic, the basic logic circuits are only limited by the number of gates available, which is a different ball game entirely. The number of possible interconnections in a programmable gate array, which sounds like what you are really after, would be a very large number indeed. Some processors do indeed have gate arrays built in.

Answer 10

You don't implement a logic gate just because it has functional completeness, especially if the other logic gates are natively available. You implement what tends to be used most by compilers.

NAND, NOR and XNOR are very rarely needed. Besides the classical bitwise operators AND, OR and XOR, only ANDN (~a & b) – which is not NAND (~(a & b)) – would have a practical utility. If any, a CPU should implement that (and indeed some CPUs do implement ANDN).

For explaining the practical utility of ANDN, imagine you have a bitmask that uses many bits, but you are interested only in some of those, which are the following:

enum my_flags {
    IT_IS_FRIDAY = 1,
    ...
    IT_IS_WARM = 8,
    ...
    THE_SUN_SHINES = 64,
    ...
};

Normally you want to check about your bits of interest in the bitmask whether

1. They are all set
2. At least one is set
3. At least one is not set
4. None is set

Let's start by collecting together your bits of interest:

#define BITS_OF_INTEREST (IT_IS_FRIDAY | IT_IS_WARM | THE_SUN_SHINES)

1. All bits of interest are set: bitwise ANDN + logical NOT

Let's say that you want to know if your bits of interest are all set. You can see it like as (my_bitmask & IT_IS_FRIDAY) && (my_bitmask & IT_IS_WARM) && (my_bitmask & THE_SUN_SHINES). However normally you would collapse that into

unsigned int life_is_beautiful = !(~my_bitmask & BITS_OF_INTEREST);

2. At least one bit of interest is set: bitwise AND

Now let's say that you want to know if at least one bit of interest is set. You can see it as (my_bitmask & IT_IS_FRIDAY) || (my_bitmask & IT_IS_WARM) || (my_bitmask & THE_SUN_SHINES). However normally you would collapse that into

unsigned int life_is_not_bad = my_bitmask & BITS_OF_INTEREST;

3. At least one bit of interest is not set: bitwise ANDN

Now let's say that you want to know if at least one bit of interest is not set. You can see it as !(my_bitmask & IT_IS_FRIDAY) || !(my_bitmask & IT_IS_WARM) || !(my_bitmask & THE_SUN_SHINES). However normally you would collapse that into

unsigned int life_is_imperfect = ~my_bitmask & BITS_OF_INTEREST;

4. No bit of interest is set: bitwise AND + logical NOT

Now let's say that you want to know if all bits of interest are not set. You can see it as !(my_bitmask & IT_IS_FRIDAY) && !(my_bitmask & IT_IS_WARM) && !(my_bitmask & THE_SUN_SHINES). However normally you would collapse that into

unsigned int life_is_horrible = !(my_bitmask & BITS_OF_INTEREST);

These are the common operations performed on a bitmask, plus the classical bitwise OR and XOR. I do think though that a language (which is not a CPU) should include the bitwise NAND, NOR and XNOR operators (whose symbols would be ~&, ~| and ~^), despite rarely used. I would not include the ANDN operator in a language though, since it's not commutative (a ANDN b is not the same as b ANDN a) – better to write ~a & b instead of a ANDN b, the former shows more clearly the asimmetry of the operation.