7 ms·

Article is interesting but short. It is pretty interesting question, but I am still missing the answer for it! (Probably: It does not use all instructions.)

by jiri 4y ago

CodesInChaos 4y ago
> Nobody really seems to know how many x86 instructions there are, but someone counted 678, meaning there are over 200 instructions that do not occur even once in all the code in my /usr/bin.
- deckard1 4y ago
  That linked stackoverflow was a bit silly and misleading. They admitted they were too lazy to count the instructions given in Intel's manual. Of course we know how many instructions there are. Assemblers (e.g. NASM) have to know what instructions exist if Intel or AMD want people to use them. There are undocumented and dead vendor instructions that nobody cares about (3DNow, Cyrix maybe?) But we definitely know all officially available instructions because they are all in Intel's manual.
  - innocenat 4y ago
    The main problem is what is a definition of an "instruction"? For example, let see the MOV instruction. How many instruction do you count it as? Intel manual listed 2 variants of MOV using the same mnemonic. One for general register, and another for control register. But if are also consider GNU AT&T syntax, then we have movb, movw, movl, movq, and movs, depend on operarand size. Do you count as 5 or 1? To make the matter more complex, movd and movq in GNU can also be used for MMX/SSE register, while Intel listed MOVD and MOVQ as seperate instructions for MMX/SSE (but they also list MOVD and MOVQ in the same section). How many do we count? If you think all of these are silly and a move is a move, do you also count MOVDQA and MOVDQU as the same (MOVDQA works only with aligned 128-bit data, while MOVDQU also works with unaligned data). How about the VEX prefixed version, VMOVDQA and VMOVDQU, that works exactly the same but has no penalty when use in stream of VEX-prefixed instructions? If we count by actual machine code, then there are like 10+ variations of MOV instruction depend on the operands. (And I still probably have forgotten about a few more MOVxxx instructions) The linked stackoverflow is a little bit silly, yes, but we actually cannot count how many instructions there are in x86/amd64.
    - plopfill 4y ago
      Indeed. This page has some more discussion of the complexities: <https://fgiesen.wordpress.com/2016/08/25/how-many-x86-instructions-are-there/ https://fgiesen.wordpress.com/2016/08/25/how-many-x86-instru...>
    - deckard1 4y ago
      > But if are also consider GNU AT&T syntax Why, though? The official x86 syntax is Intel syntax. In any case, it doesn't matter. Every possible encoding of each mnemonic is given in Intel's manual. This whole business about "what is an instruction anyway" is just sophistry. Anyone using gas would hopefully know how the AT&T syntax is mapping to Intel encodings. > but we actually cannot count how many instructions there are in x86/amd64. Again, you can. It's quite simple. Define an instruction how ever you want, and then go and look at the manual. It's a finite known set. Intel isn't hiding this info.
      - innocenat 4y ago
        Maybe I was not clear. The problem is that no one is going to agree to the same definition. I have already listed several points where disagreements may occurs, and that is just the surface of the complexity.
    - jsjohnst 4y ago
      > but we actually cannot count how many instructions there are in x86/amd64 Sorry for being pedantic, but we can, if everyone agrees on what is actually being counted, aka what the definition of an “instruction” is. You already made the case supporting that POV yourself, then oddly flipped back to implying there was something preventing it besides that at the end. We definitely “can” agree on a definition of an “instruction”, but yes, we probably won’t.
      - innocenat 4y ago
        That's a big "if". We can't even get a single assembly syntax, and Intel vs GNU/AT&T syntax war is almost as bad as vi/emac.
dvt 4y ago
The answer is obviously "no" because there's no such thing as "the set of all x86 instructions." Every vendor has many vendor-specific x86 extensions inside their microcode, some of which end up being adopted by all other vendors (essentially becoming "canonized" as x86 proper). In some cases, these extensions are widely accepted (like x86-64, which was initially developed by AMD, hence its amd64 moniker). In other cases, these extensions die a quiet death, like 3DNow! (also one of AMD's extensions, introduced in their K6-2 line). And in other cases, extensions are only implemented for specific lines of processors (Xeons famously include AVX-512[1]). To look at a more concrete exemplification of this, gcc has both AVX-512 and 3DNow! flags[2] (because it was around back in 1998), while go only has AVX-512 flags (and doesn't care about deprecated extensions like 3DNow!). [1] https://colfaxresearch.com/skl-avx512/ https://colfaxresearch.com/skl-avx512/ [2] https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html
duskwuff 4y ago
> It is pretty interesting question, but I am still missing the answer for it! In a very literal sense, the answer is trivially yes, because the compiler can be forced to generate any instruction sequence in an inline assembly block. But assuming that isn't what you mean, there are plenty of instructions that the compiler will never emit when compiling CPU-independent C code (i.e. no inline assembly or CPU-specific compiler intrinsics). These fall into a few general categories: 1) Privileged instructions, like IN/OUT, WAIT, or SGDT. These instructions aren't even usable outside the kernel, and there's no way to represent their effects in pure C anyway. 2) Instructions which interact with specific hardware capabilities of the CPU, like the AES/SHA instructions, CPUID, RDTSC, or PREFETCH. Much like the privileged instructions, there's no way to represent their effects in C. 3) 8086 legacy instructions like ENTER, LOOP, or XLAT, which operate on 16-bit registers in highly inflexible ways, making them awkward for a compiler to generate code around. Most of them are also microcoded, making them slower than equivalent code sequences -- so there's no reason to use them anyway. 4) Instructions which interact directly with the flags register, like LAHF or PUSHF. C code doesn't have any concept of the flags register, and most compilers only generate flag-dependent instructions immediately after setting flags (e.g. in CMP/Jcc sequences), so they never need to save/restore flags. 5) Complex SIMD instructions like PSHUFB or PUNPCKxx which modern compilers can't reason deeply enough about your code to use effectively. (I'd love to be proven wrong on this one!)
- hakfoo 4y ago
  There's definitely been a "death spiral" for some of these instructions. Nobody used "LOOP", for example, so it tended to be poorly optimized, which made compilers even less likely to use it-- just use the seperate instructions that have similar effects. Eventually it actually became a liability to run it efficiently. (The famous "Windows 95 won't work right on a fast K6-2" bug is based on this problem-- LOOP was much less efficient on a Pentium than a K6)
  - nemothekid 4y ago
    >The famous "Windows 95 won't work right on a fast K6-2" bug is based on this problem Wow that's pretty interesting on it's own. It turns out a program was trying to figure out long the LOOP instruction would take to run by running it 2^20 times and dividing it by the amount of time taken in milliseconds. On a Pentium 3 this took 17ms, but on a K-2 (and faster) this could take 0 milliseconds. https://gigazine.net/gsc_news/en/20200606-windows95-failed-start/ https://gigazine.net/gsc_news/en/20200606-windows95-failed-s...

Article is interesting but short. It is pretty interesting question, but I am still missing the answer for it! (Probably: It does not use all instructions.)

by jiri 4y ago

Article is interesting but short. It is pretty interesting question, but I am still missing the answer for it! (Probably: It does not use all instructions.)

CodesInChaos 4y ago

> Nobody really seems to know how many x86 instructions there are, but someone counted 678, meaning there are over 200 instructions that do not occur even once in all the code in my /usr/bin.

deckard1 4y ago
That linked stackoverflow was a bit silly and misleading. They admitted they were too lazy to count the instructions given in Intel's manual. Of course we know how many instructions there are. Assemblers (e.g. NASM) have to know what instructions exist if Intel or AMD want people to use them. There are undocumented and dead vendor instructions that nobody cares about (3DNow, Cyrix maybe?) But we definitely know all officially available instructions because they are all in Intel's manual.
- innocenat 4y ago
  The main problem is what is a definition of an "instruction"? For example, let see the MOV instruction. How many instruction do you count it as? Intel manual listed 2 variants of MOV using the same mnemonic. One for general register, and another for control register. But if are also consider GNU AT&T syntax, then we have movb, movw, movl, movq, and movs, depend on operarand size. Do you count as 5 or 1? To make the matter more complex, movd and movq in GNU can also be used for MMX/SSE register, while Intel listed MOVD and MOVQ as seperate instructions for MMX/SSE (but they also list MOVD and MOVQ in the same section). How many do we count? If you think all of these are silly and a move is a move, do you also count MOVDQA and MOVDQU as the same (MOVDQA works only with aligned 128-bit data, while MOVDQU also works with unaligned data). How about the VEX prefixed version, VMOVDQA and VMOVDQU, that works exactly the same but has no penalty when use in stream of VEX-prefixed instructions? If we count by actual machine code, then there are like 10+ variations of MOV instruction depend on the operands. (And I still probably have forgotten about a few more MOVxxx instructions) The linked stackoverflow is a little bit silly, yes, but we actually cannot count how many instructions there are in x86/amd64.
  - plopfill 4y ago
    Indeed. This page has some more discussion of the complexities: <https://fgiesen.wordpress.com/2016/08/25/how-many-x86-instructions-are-there/ https://fgiesen.wordpress.com/2016/08/25/how-many-x86-instru...>
  - deckard1 4y ago
    > But if are also consider GNU AT&T syntax Why, though? The official x86 syntax is Intel syntax. In any case, it doesn't matter. Every possible encoding of each mnemonic is given in Intel's manual. This whole business about "what is an instruction anyway" is just sophistry. Anyone using gas would hopefully know how the AT&T syntax is mapping to Intel encodings. > but we actually cannot count how many instructions there are in x86/amd64. Again, you can. It's quite simple. Define an instruction how ever you want, and then go and look at the manual. It's a finite known set. Intel isn't hiding this info.
    - innocenat 4y ago
      Maybe I was not clear. The problem is that no one is going to agree to the same definition. I have already listed several points where disagreements may occurs, and that is just the surface of the complexity.
  - jsjohnst 4y ago
    > but we actually cannot count how many instructions there are in x86/amd64 Sorry for being pedantic, but we can, if everyone agrees on what is actually being counted, aka what the definition of an “instruction” is. You already made the case supporting that POV yourself, then oddly flipped back to implying there was something preventing it besides that at the end. We definitely “can” agree on a definition of an “instruction”, but yes, we probably won’t.
    - innocenat 4y ago
      That's a big "if". We can't even get a single assembly syntax, and Intel vs GNU/AT&T syntax war is almost as bad as vi/emac.

dvt 4y ago

The answer is obviously "no" because there's no such thing as "the set of all x86 instructions." Every vendor has many vendor-specific x86 extensions inside their microcode, some of which end up being adopted by all other vendors (essentially becoming "canonized" as x86 proper). In some cases, these extensions are widely accepted (like x86-64, which was initially developed by AMD, hence its amd64 moniker). In other cases, these extensions die a quiet death, like 3DNow! (also one of AMD's extensions, introduced in their K6-2 line). And in other cases, extensions are only implemented for specific lines of processors (Xeons famously include AVX-512[1]). To look at a more concrete exemplification of this, gcc has both AVX-512 and 3DNow! flags[2] (because it was around back in 1998), while go only has AVX-512 flags (and doesn't care about deprecated extensions like 3DNow!). [1] https://colfaxresearch.com/skl-avx512/ https://colfaxresearch.com/skl-avx512/ [2] https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html https://gcc.gnu.org/onlinedocs/gcc/x86-Options.html

duskwuff 4y ago

> It is pretty interesting question, but I am still missing the answer for it! In a very literal sense, the answer is trivially yes, because the compiler can be forced to generate any instruction sequence in an inline assembly block. But assuming that isn't what you mean, there are plenty of instructions that the compiler will never emit when compiling CPU-independent C code (i.e. no inline assembly or CPU-specific compiler intrinsics). These fall into a few general categories: 1) Privileged instructions, like IN/OUT, WAIT, or SGDT. These instructions aren't even usable outside the kernel, and there's no way to represent their effects in pure C anyway. 2) Instructions which interact with specific hardware capabilities of the CPU, like the AES/SHA instructions, CPUID, RDTSC, or PREFETCH. Much like the privileged instructions, there's no way to represent their effects in C. 3) 8086 legacy instructions like ENTER, LOOP, or XLAT, which operate on 16-bit registers in highly inflexible ways, making them awkward for a compiler to generate code around. Most of them are also microcoded, making them slower than equivalent code sequences -- so there's no reason to use them anyway. 4) Instructions which interact directly with the flags register, like LAHF or PUSHF. C code doesn't have any concept of the flags register, and most compilers only generate flag-dependent instructions immediately after setting flags (e.g. in CMP/Jcc sequences), so they never need to save/restore flags. 5) Complex SIMD instructions like PSHUFB or PUNPCKxx which modern compilers can't reason deeply enough about your code to use effectively. (I'd love to be proven wrong on this one!)

hakfoo 4y ago
There's definitely been a "death spiral" for some of these instructions. Nobody used "LOOP", for example, so it tended to be poorly optimized, which made compilers even less likely to use it-- just use the seperate instructions that have similar effects. Eventually it actually became a liability to run it efficiently. (The famous "Windows 95 won't work right on a fast K6-2" bug is based on this problem-- LOOP was much less efficient on a Pentium than a K6)
- nemothekid 4y ago
  >The famous "Windows 95 won't work right on a fast K6-2" bug is based on this problem Wow that's pretty interesting on it's own. It turns out a program was trying to figure out long the LOOP instruction would take to run by running it 2^20 times and dividing it by the amount of time taken in milliseconds. On a Pentium 3 this took 17ms, but on a K-2 (and faster) this could take 0 milliseconds. https://gigazine.net/gsc_news/en/20200606-windows95-failed-start/ https://gigazine.net/gsc_news/en/20200606-windows95-failed-s...