52
\$\begingroup\$

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

\$\endgroup\$
  • 20
    \$\begingroup\$ What usecase do you have for the nand instruction? Probably x86 designers never found any \$\endgroup\$ – PlasmaHH Jan 17 '17 at 16:20
  • 16
    \$\begingroup\$ ARM has the BIC instruction, which is a & ~b. Arm Thumb-2 has the ORN instruction which is ~(a | b). ARM is pretty modern. Encoding an instruction in the CPU instruction set has its costs. So only the most "useful" ones are making their way into ISA. \$\endgroup\$ – Eugene Sh. Jan 17 '17 at 16:47
  • 24
    \$\begingroup\$ @Amumu We could have ~(((a << 1) | (b >> 1)) | 0x55555555) instruction too. The purpose would be so that ~(((a << 1) | (b >> 1)) | 0x55555555) can be translated into a single instruction instead of 6. So, why not? \$\endgroup\$ – immibis Jan 17 '17 at 21:07
  • 11
    \$\begingroup\$ @Amumu: Thats not a usecase, and also its ~ not !. A usecase is a compelling reason why that instruction is useful, and where it can be applied. Your reasoning is like saying "The instruction should be there so it can be used" but the question is "what to use it for that is so important that its useful to spend resources". \$\endgroup\$ – PlasmaHH Jan 18 '17 at 8:38
  • 4
    \$\begingroup\$ I've been programming for 45 years, written a few compilers, and used some wierd logical operators when available such as IMP, but I've never had a use for a NAND operator or instruction. \$\endgroup\$ – user207421 Jan 19 '17 at 0:48

10 Answers 10

62
\$\begingroup\$

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.

\$\endgroup\$
  • 4
    \$\begingroup\$ @supercat AND-NOT is commonly used to turn off bits in a bit-set variable. e.g. if(windowType & ~WINDOW_RESIZABLE) { ... do stuff for variable-sized windows ... } \$\endgroup\$ – adib Jan 17 '17 at 21:23
  • 2
    \$\begingroup\$ @adib: Yup. An interesting feature of "and-not" is that unlike the "bitwise not" operator [~] the result size won't matter. If foo is a uint64_t, the statement foo &= ~something; may sometimes clear out more bits than intended, but if there were a &~= operator such problems could be avoided. \$\endgroup\$ – supercat Jan 17 '17 at 21:46
  • 6
    \$\begingroup\$ @adib if WINDOW_RESIZABLE is a constant, then an optimizer should evaluate ~WINDOW_RESIZABLEat compile time, so this is just an AND at run time. \$\endgroup\$ – alephzero Jan 17 '17 at 22:49
  • 4
    \$\begingroup\$ @MarkRansom: No, the cause-and effect is entirely correct from computing history. This phenomena of designing CPUs that are optimized for compilers instead of human assembly programmers was part of the RISC movement (though, the RISC movement itself is wider than just that aspect). CPUs designed for compilers include the ARM and Atmel AVR. In the late 90s and early 00s people hired compiler writers and OS programmers to design CPU instruction sets \$\endgroup\$ – slebetman Jan 18 '17 at 4:45
  • 3
    \$\begingroup\$ These days register-to-register operations are essentially free compared to RAM access. Implementing redundant instructions costs silicon real-estate in the CPU. Therefore there will usually be just one form of bitwise-OR and of bitwise-AND because adding a bitwise-complement register-register operation will hardly ever slow anything down. \$\endgroup\$ – nigel222 Jan 18 '17 at 18:38
32
\$\begingroup\$

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.

\$\endgroup\$
29
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ In cases where input isolation isn't required, "and not" would seem very cheap in hardware. Back in 1977 I designed a turn-signal controller for my parent's trailer using two transistors and two diodes per light to perform an "XOR" function [left lamp == xor(left signal, brake); right lamp == xor(right signal, brake)], essentially wire-or'ing two and-not functions for each light. I haven't see such tricks used in LSI design, but I would think that in TTL or NMOS, in cases where whatever's feeding an input would ahve adequate drive capability, such tricks could save circuitry. \$\endgroup\$ – supercat Jan 18 '17 at 18:24
12
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
10
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Indeed - the choice of conditional jump instruction gives you a choice of inverting and non-inverting logic for a whole class of operations, without having to implement that choice for each individually. \$\endgroup\$ – Chris Stratton Jan 21 '17 at 1:32
  • \$\begingroup\$ This should've been the best answer. The zero flag operations makes NAND superfluous for logical operations as AND+JNZ and AND+JZ are essentially short circuited/logical AND and NAND respectively, both takes the same number of opcode. \$\endgroup\$ – Lie Ryan Jan 22 '17 at 20:47
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ nop can't implement all other logic gates, but nand or nor can, effectively recreate any instruction that is implemented in a CPU in software. If we take the RISC approach, that is.. \$\endgroup\$ – Amumu Jan 18 '17 at 20:17
  • \$\begingroup\$ @Amumu I think you're mixing up gate and instruction. Gates are used to implement instructions, not the other way around. NOP is an instruction, not a gate. And yes, CPUs contain thousands or maybe even millions of NAND gates to implement all the instructions. Just not the "NAND" instruction. \$\endgroup\$ – Agent_L Jan 19 '17 at 11:13
  • 2
    \$\begingroup\$ @Amumu That's not the RISC approach :) That's the "use the widest abstractions" approach, which isn't too useful outside of very specific applications. Sure, nand is one gate that can be used to implement other gates; but you already have all the other instructions. Reimplementing them using a nand instruction would be slower. And they are used far too often to tolerate that, unlike your cherry-picked specific example where nand would produce shorter code (not faster code, just shorter); but that's extremely rare, and the benefit is simply not worth the cost. \$\endgroup\$ – Luaan Jan 19 '17 at 11:48
  • \$\begingroup\$ @Amumu If we used your approach, we wouldn't have positional numbers. What's the point when you can simply say ((((())))) instead of 5, right? Five is only one specific number, that's way too limiting - sets are far more general :P \$\endgroup\$ – Luaan Jan 19 '17 at 11:50
  • \$\begingroup\$ @Agent_L Yes, I know gates implement instructions. nand implements all gates, therefore implicitly nand can implement all other instructions. Then, if a programmer has a nand instruction available, he can invent his own instructions when thinking in logic gates. What I meant from the beginning is that if it is so fundamental, why it wasn't given its own instruction (that is, an opcode in decoder logic), so a programmer can use such instruction. Of course after I got answered, now I know it depends on the software usage. \$\endgroup\$ – Amumu Jan 20 '17 at 6:00
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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.