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

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.

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.

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 short-circuit. So usually a branch-based approach to implementing them is needed. Even when the compiler could prove that short-circuit vs complete evaluation makes no difference to program behaviour the operands for the logical operations are usually not in a conviniant form to implement the expression using the bitwise asm operations.

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.