10 ms·

Does a compiler use all x86 instructions? (2016)

103 points by davidgerard 4y ago

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...
wruza 4y ago
why there are so many lea LEA does addressing math without an actual fetch/store. Which is base + k * n + offset Every time you put & before an lvalue there is a chance for LEA. https://stackoverflow.com/questions/1658294/whats-the-purpose-of-the-lea-instruction https://stackoverflow.com/questions/1658294/whats-the-purpos...
- andreareina 4y ago
  IIRC it's also (ab?)used for a lot of actual math that has that pattern, which is a lot.
  - adgjlsfhk1 4y ago
    it's basically the Internet equivalent of fma which is the best floating point instruction.
    - mtklein 4y ago
      I think you maybe meant to say “integer”?
      - adgjlsfhk1 4y ago
        yes. yes I did.
    - orlp 4y ago
      Unfortunately compilers can't emit FMA instructions from regular floating point math without specifying (an equivalent of) `-ffast-math` as its results aren't identical to a*b + c done with two instructions.
      - thxg 4y ago
        > Unfortunately compilers can't emit FMA instructions from regular floating point math without specifying (an equivalent of) `-ffast-math` ... if you specify an ISO language standard (e.g. -std=c99). By default, in GNU mode, gcc will happily emit FMA at -O3. From the man page: By default, -fexcess-precision=fast is in effect; this means that operations may be carried out in a wider precision than the types specified in the source if that would result in faster code, and it is unpredictable when rounding to the types specified in the source code takes place. [...] [-fexcess-precision=standard] is enabled by default for C if a strict conformance option such as -std=c99 is used. > Unfortunately compilers can't emit FMA instructions without specifying [-ffast-math] I would argue that it would have been fortunate if FMA was disabled by default. And that it is unfortunate that it is not. Yes, FMA has a performance boost and (usually) better accuracy... But it comes at the cost of bit-for-bit reproducibility. If we let the compiler automatically decide when to apply FMA, then a compiler upgrade or even unrelated code changes could lead to slightly different results as rounding is performed at different points in the computation. For numerical codes in which small perturbations can yield wildly different solution paths, debugging can become a nightmare. Of course this is a subjective preference and it strongly depends on the application domain. I agree that for some people defaulting to best performance at -O3 is the right choice.
29athrowaway 4y ago
If you build a binary locally, you may enable the use of instruction sets that your processor supports. When you download a x86 binary, it will likely stick to the subset of instructions that most processors have.
- klodolph 4y ago
  The subset that most have is going to be pretty broad. These days, you'd definitely assume that processors have SSE2, for example. However, most SSE2 instructions won't be emitted by GCC until you crank things up to -O3.
  - duskwuff 4y ago
    > These days, you'd definitely assume that processors have SSE2, for example. In fact, x86_64 specifically guarantees the availability of SSE2.
  - josefx 4y ago
    Not surprising, after all C doesn't have vector math. There is no way to make sensible use of these instructions without the compiler significantly altering the program flow first.
    - klodolph 4y ago
      Using -O3 is a very sensible way to use vector instructions, in practice. It’s not universally good. It’s just that if you take naïve C code that does bulk operations on arrays, and compile it at -O3, you might get a very nice improvement from the auto-vectorizer. With some additional restrict keyword annotations, you can sometimes improve the performance significantly. Then there are non-standard tricks you can use, like __builtin_assume_aligned(). This is something of an arcane art. Sometimes it just doesn’t work at all, sometimes it’s not obvious how to write your code so that the autovectorizer can work well, and getting the autovectorizer to work requires enabling various code transformation passes that will often make code worse. However, it’s still worth using, because when your function does autovectorize well, it saves you a ton of work trying to vectorize it manually.
_8j50 4y ago
Something I heard a while back is that very roughly 90%+ of compiler generated code is made up of 19 instructions and the rest are rare enough that you on x86/64 you shouldn't memorize them, just keep the manual handy. I wonder if that included various variations of instructions. But I am very curious about OPs question now. Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind.
- rurban 4y ago
  /usr/bin has certainly no -march=native extensions, not even SIMD. It's extremely conservative, unless you are using Gentoo (nobody does anymore). /usr/local/bin with tuned CFLAGS sounds better for such a statistical analysis.
- duskwuff 4y ago
  > Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind. For what it's worth, this is largely unnecessary nowadays. Tuning for a specific processor used to allow the compiler to use instruction scheduling and enabled use of SSE instructions. However: 1) Modern x86 CPUs all use out-of-order execution, making instruction scheduling unnecessary. (Some older Atom CPUs are in-order, but their performance is pretty awful even with instruction scheduling.) 2) If you're building for x86_64, you can assume a certain baseline of instruction set support -- in particular, CMOV, SSE, and SSE2 instructions are always available on any 64-bit CPU. While these don't cover all instructions, it does cover the bulk of what the compiler is likely to want to generate in typical application code.
  - crest 4y ago
    Instruction placement and scheduling is still important on OoO cores e.g. splitting a function intentionally over multiple pages to keep the commonly used parts of functions used together in less pages which helps with instruction cache utilisation and iTLB pressure. Lots of high performance microarchitectures use assumptions about control flow for optimisation e.g. use the direction (backward, forward) of conditional jumps and branches as weak prediction, convert conditional branches over a single instruction into predicated execution, fuse common instruction pairs into a single micro-operation. At least limited cooperation between compiler and CPU core is required to make good use of those features.
deleted 4y ago
[deleted]
chungy 4y ago
Article might raise an interesting question, but the methodology used to determine if his system's binaries use the entire available set of instructions is dubious at best. He doesn't describe what operating system or distribution he is running, or how the binaries were built at all. If it's on Gentoo with all the optimization settings tweaked out, it may be useful data. If it's on something like Debian where binaries are built to a lowest common denominator, that's... much less useful.
- johannes1234321 4y ago
  > If it's on something like Debian where binaries are built to a lowest common denominator, that's... much less useful. Depending on the point one wants to make. Only very few people will run maxed out Gentoo builds, but there is a huge number of people running debian and red hat derived distributions. Thus findings there represent what is in broad use.
- nwallin 4y ago
  On my Gentoo system with `-march=znver2` and `-ftree-vectorize` set, I ran: find /usr/bin /usr/lib64 -type f -executable -or -name '*.so*' -exec objdump -d '{}' + | cut -f3 | grep -oE "^[a-z]+" | sort | uniq -c Which should find all executables and shared libraries. It found 1174 instructions. So ballpark 3 times as many instructions as on his system, and twice as many as the number of instructions he claims to exist. So you're right; suffice to say his methodology has some holes in it. Interestingly xor got dropped from 6th place on his list to 11th on mine. My list upgraded jmp to 4th place: above 5th place je, which surprised me. His objdump calling convention appears to be different than mind; he's seeing the `callq`, `jmpq`, and `retq` instructions, I get `call`, `jmp`, and `ret`. I don't know what that means.
  - stefantalpalaru 4y ago
  - adrian_b 4y ago
    The mnemonics ending in -q just specify explicitly that they are 64-bit (quad-word, where "word" was 16-bit on Intel 8088) instructions, while the size of the mnemonics without -q is specified implicitly by a previous assembler directive. Also on a Gentoo system, even when searching just on /usr/bin I have seen a result similar to yours, with plenty of AVX instructions. This is expected, because our executables have been compiled for a modern CPU, while those of the author have been compiled for a generic 64-bit CPU, i.e. 20-years old. The high frequency of "jmp", which I have noticed too, can come e.g. from a higher proportion of "if ... else ..." versus simple "if", or from a higher proportion of "switch" versus "if", or from some compiler that does tail-call optimization. The methodology is OK for determining the static frequency of instructions, which determines the size of a program. The dynamic frequency of instructions, which influences the execution time, can be very different, because many computational instructions are mostly used either in loops or in frequently invoked functions, so their static frequency can be orders of magnitude less than their dynamic frequency. To the one-liner it is convenient to add at the end " | sort -n ", to get the list of mnemonics already sorted by frequency.
benlivengood 4y ago
There are still instructions for binary coded decimal arithmetic in our 64-bit superscalar multicore processors (although they throw #UD in 64-bit mode). DAA and AAA for addition, DAS and AAS for subtraction, AAM for multiplication, AAD for division. The software interrupts (INT) were almost universally replaced with SYSENTER and SYSCALL (and their SYSEXIT/SYSRET counterparts). ENTER and LEAVE instructions for manipulating the stack for function calls are slower than direct modification of *SP and *BP. The extra segment registers (ES, FS, and GS) are nearly useless in flat memory model (CS, DS, ES, and SS must be equal for practical purposes). Thread local storage uses FS in Linux, and the kernel uses GS for per-cpu data structures. It looks like BSD may use GS for thread local storage.
- mkup 4y ago
  I've recently observed gcc 10.x emitting LEAVE instruction in functions using __builtin_alloca or __attribute__(( force_align_arg_pointer )), although only for x86_64 targets (for i686 it's still MOV ESP, EBP / POP EBP pair).
  - leeter 4y ago
    I looked this up once, LEAVE is fast but ENTER is slower than just doing it by hand. So compilers will use LEAVE under some circumstances but ENTER is a dead instruction AFAIK, just like LOOP and a few others.
- p_l 4y ago
  FS and GS are used by windows APIs, 286 segmentation model was used to play with stuff before NX became a thing though (or VT-x/SVM)
- rep_lodsb 4y ago
  How to convert an integer to hex digit in 5 bytes: ; AL in range 0..35 (usually 0..15) cmp al,10 sbb al,0x69 das ; AL = '0'..'9', 'A'..'Z' (equivalent code also works on the Z80. Maybe also with the 6502's decimal mode?) The oldest and least used feature is probably the parity flag. It originally came from the Datapoint 2200 terminal, and still exists even in 64-bit mode!
junon 4y ago
Depends on the compiler. LGDT is probably never emitted by the compiler, no.
rep_movsd 4y ago
LEA is used for calculating integer A + B * C in one instruction for C that is 1, 2 or 4 It is meant for calculating array index addresses base+index*itemsize but was found by many assembly programmers of the early days to be useful for general arithmetic. All compilers use this trick
dathinab 4y ago
sometimes I wonder if just shipping a 64bit only no legacy instructions (i.e. cleaned up x86_64) instruction set would put a stop to the ARM is fundamentally better discussion (and sure there is ARM with legacy instructions etc. but Apple silicon is 64bit no legacy cruft AFIK).
- jsjohnst 4y ago
  > sometimes I wonder if just shipping a 64bit only no legacy instructions (i.e. cleaned up x86_64) instruction set would put a stop to the ARM is fundamentally better discussion No > but Apple silicon is 64bit no legacy cruft AFIK No. It’s an ARMv8 ISA, legacy cruft and all.
  - hajile 4y ago
    uaarch64 has very little legacy stuff left. When ARM announced A715, they got rid of uaarch32 and said it got them a 75% reduction in the size of the decoder while increasing the width of the decoder from 4 to 5-wide. They even got rid of the uop-cache because the new encoding was so much smaller and efficient that it didn't make sense to keep it around.
  - dathinab 4y ago
    through its A64 only (no T32 neither A32) which cuts out a lot of legacy instructions/instruction variants. Doing the same for x86_64 would be a bit like no 16bit and 32bit specific machine instructions/instruction variants, no support for legacy bios things etc.
MichaelMoser123 4y ago
There are even more instructions: see this lecture on finding undocumented instructions https://www.youtube.com/watch?v=KrksBdWcZgQ https://www.youtube.com/watch?v=KrksBdWcZgQ
- uberman 4y ago
  Highly recommend watching this as it was a great presentation. Thank you for posting this

103 points by davidgerard 4y ago

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

wruza 4y ago

why there are so many lea LEA does addressing math without an actual fetch/store. Which is base + k * n + offset Every time you put & before an lvalue there is a chance for LEA. https://stackoverflow.com/questions/1658294/whats-the-purpose-of-the-lea-instruction https://stackoverflow.com/questions/1658294/whats-the-purpos...

andreareina 4y ago
IIRC it's also (ab?)used for a lot of actual math that has that pattern, which is a lot.
- adgjlsfhk1 4y ago
  it's basically the Internet equivalent of fma which is the best floating point instruction.
  - mtklein 4y ago
    I think you maybe meant to say “integer”?
    - adgjlsfhk1 4y ago
      yes. yes I did.
  - orlp 4y ago
    Unfortunately compilers can't emit FMA instructions from regular floating point math without specifying (an equivalent of) `-ffast-math` as its results aren't identical to a*b + c done with two instructions.
    - thxg 4y ago
      > Unfortunately compilers can't emit FMA instructions from regular floating point math without specifying (an equivalent of) `-ffast-math` ... if you specify an ISO language standard (e.g. -std=c99). By default, in GNU mode, gcc will happily emit FMA at -O3. From the man page: By default, -fexcess-precision=fast is in effect; this means that operations may be carried out in a wider precision than the types specified in the source if that would result in faster code, and it is unpredictable when rounding to the types specified in the source code takes place. [...] [-fexcess-precision=standard] is enabled by default for C if a strict conformance option such as -std=c99 is used. > Unfortunately compilers can't emit FMA instructions without specifying [-ffast-math] I would argue that it would have been fortunate if FMA was disabled by default. And that it is unfortunate that it is not. Yes, FMA has a performance boost and (usually) better accuracy... But it comes at the cost of bit-for-bit reproducibility. If we let the compiler automatically decide when to apply FMA, then a compiler upgrade or even unrelated code changes could lead to slightly different results as rounding is performed at different points in the computation. For numerical codes in which small perturbations can yield wildly different solution paths, debugging can become a nightmare. Of course this is a subjective preference and it strongly depends on the application domain. I agree that for some people defaulting to best performance at -O3 is the right choice.

29athrowaway 4y ago

If you build a binary locally, you may enable the use of instruction sets that your processor supports. When you download a x86 binary, it will likely stick to the subset of instructions that most processors have.

klodolph 4y ago
The subset that most have is going to be pretty broad. These days, you'd definitely assume that processors have SSE2, for example. However, most SSE2 instructions won't be emitted by GCC until you crank things up to -O3.
- duskwuff 4y ago
  > These days, you'd definitely assume that processors have SSE2, for example. In fact, x86_64 specifically guarantees the availability of SSE2.
- josefx 4y ago
  Not surprising, after all C doesn't have vector math. There is no way to make sensible use of these instructions without the compiler significantly altering the program flow first.
  - klodolph 4y ago
    Using -O3 is a very sensible way to use vector instructions, in practice. It’s not universally good. It’s just that if you take naïve C code that does bulk operations on arrays, and compile it at -O3, you might get a very nice improvement from the auto-vectorizer. With some additional restrict keyword annotations, you can sometimes improve the performance significantly. Then there are non-standard tricks you can use, like __builtin_assume_aligned(). This is something of an arcane art. Sometimes it just doesn’t work at all, sometimes it’s not obvious how to write your code so that the autovectorizer can work well, and getting the autovectorizer to work requires enabling various code transformation passes that will often make code worse. However, it’s still worth using, because when your function does autovectorize well, it saves you a ton of work trying to vectorize it manually.

_8j50 4y ago

Something I heard a while back is that very roughly 90%+ of compiler generated code is made up of 19 instructions and the rest are rare enough that you on x86/64 you shouldn't memorize them, just keep the manual handy. I wonder if that included various variations of instructions. But I am very curious about OPs question now. Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind.

rurban 4y ago
/usr/bin has certainly no -march=native extensions, not even SIMD. It's extremely conservative, unless you are using Gentoo (nobody does anymore). /usr/local/bin with tuned CFLAGS sounds better for such a statistical analysis.
duskwuff 4y ago
> Moreover, can you influence GCC over what instructions it emits? On Gentoo for example, you can setup your make file so that the while system is compiled with your specific processor in mind. For what it's worth, this is largely unnecessary nowadays. Tuning for a specific processor used to allow the compiler to use instruction scheduling and enabled use of SSE instructions. However: 1) Modern x86 CPUs all use out-of-order execution, making instruction scheduling unnecessary. (Some older Atom CPUs are in-order, but their performance is pretty awful even with instruction scheduling.) 2) If you're building for x86_64, you can assume a certain baseline of instruction set support -- in particular, CMOV, SSE, and SSE2 instructions are always available on any 64-bit CPU. While these don't cover all instructions, it does cover the bulk of what the compiler is likely to want to generate in typical application code.
- crest 4y ago
  Instruction placement and scheduling is still important on OoO cores e.g. splitting a function intentionally over multiple pages to keep the commonly used parts of functions used together in less pages which helps with instruction cache utilisation and iTLB pressure. Lots of high performance microarchitectures use assumptions about control flow for optimisation e.g. use the direction (backward, forward) of conditional jumps and branches as weak prediction, convert conditional branches over a single instruction into predicated execution, fuse common instruction pairs into a single micro-operation. At least limited cooperation between compiler and CPU core is required to make good use of those features.

deleted 4y ago

[deleted]

chungy 4y ago

Article might raise an interesting question, but the methodology used to determine if his system's binaries use the entire available set of instructions is dubious at best. He doesn't describe what operating system or distribution he is running, or how the binaries were built at all. If it's on Gentoo with all the optimization settings tweaked out, it may be useful data. If it's on something like Debian where binaries are built to a lowest common denominator, that's... much less useful.

johannes1234321 4y ago
> If it's on something like Debian where binaries are built to a lowest common denominator, that's... much less useful. Depending on the point one wants to make. Only very few people will run maxed out Gentoo builds, but there is a huge number of people running debian and red hat derived distributions. Thus findings there represent what is in broad use.
nwallin 4y ago
On my Gentoo system with `-march=znver2` and `-ftree-vectorize` set, I ran: find /usr/bin /usr/lib64 -type f -executable -or -name '*.so*' -exec objdump -d '{}' + | cut -f3 | grep -oE "^[a-z]+" | sort | uniq -c Which should find all executables and shared libraries. It found 1174 instructions. So ballpark 3 times as many instructions as on his system, and twice as many as the number of instructions he claims to exist. So you're right; suffice to say his methodology has some holes in it. Interestingly xor got dropped from 6th place on his list to 11th on mine. My list upgraded jmp to 4th place: above 5th place je, which surprised me. His objdump calling convention appears to be different than mind; he's seeing the `callq`, `jmpq`, and `retq` instructions, I get `call`, `jmp`, and `ret`. I don't know what that means.
- stefantalpalaru 4y ago
- adrian_b 4y ago
  The mnemonics ending in -q just specify explicitly that they are 64-bit (quad-word, where "word" was 16-bit on Intel 8088) instructions, while the size of the mnemonics without -q is specified implicitly by a previous assembler directive. Also on a Gentoo system, even when searching just on /usr/bin I have seen a result similar to yours, with plenty of AVX instructions. This is expected, because our executables have been compiled for a modern CPU, while those of the author have been compiled for a generic 64-bit CPU, i.e. 20-years old. The high frequency of "jmp", which I have noticed too, can come e.g. from a higher proportion of "if ... else ..." versus simple "if", or from a higher proportion of "switch" versus "if", or from some compiler that does tail-call optimization. The methodology is OK for determining the static frequency of instructions, which determines the size of a program. The dynamic frequency of instructions, which influences the execution time, can be very different, because many computational instructions are mostly used either in loops or in frequently invoked functions, so their static frequency can be orders of magnitude less than their dynamic frequency. To the one-liner it is convenient to add at the end " | sort -n ", to get the list of mnemonics already sorted by frequency.

benlivengood 4y ago

There are still instructions for binary coded decimal arithmetic in our 64-bit superscalar multicore processors (although they throw #UD in 64-bit mode). DAA and AAA for addition, DAS and AAS for subtraction, AAM for multiplication, AAD for division. The software interrupts (INT) were almost universally replaced with SYSENTER and SYSCALL (and their SYSEXIT/SYSRET counterparts). ENTER and LEAVE instructions for manipulating the stack for function calls are slower than direct modification of *SP and *BP. The extra segment registers (ES, FS, and GS) are nearly useless in flat memory model (CS, DS, ES, and SS must be equal for practical purposes). Thread local storage uses FS in Linux, and the kernel uses GS for per-cpu data structures. It looks like BSD may use GS for thread local storage.

mkup 4y ago
I've recently observed gcc 10.x emitting LEAVE instruction in functions using __builtin_alloca or __attribute__(( force_align_arg_pointer )), although only for x86_64 targets (for i686 it's still MOV ESP, EBP / POP EBP pair).
- leeter 4y ago
  I looked this up once, LEAVE is fast but ENTER is slower than just doing it by hand. So compilers will use LEAVE under some circumstances but ENTER is a dead instruction AFAIK, just like LOOP and a few others.
p_l 4y ago
FS and GS are used by windows APIs, 286 segmentation model was used to play with stuff before NX became a thing though (or VT-x/SVM)
rep_lodsb 4y ago
How to convert an integer to hex digit in 5 bytes: ; AL in range 0..35 (usually 0..15) cmp al,10 sbb al,0x69 das ; AL = '0'..'9', 'A'..'Z' (equivalent code also works on the Z80. Maybe also with the 6502's decimal mode?) The oldest and least used feature is probably the parity flag. It originally came from the Datapoint 2200 terminal, and still exists even in 64-bit mode!

junon 4y ago

Depends on the compiler. LGDT is probably never emitted by the compiler, no.

rep_movsd 4y ago

LEA is used for calculating integer A + B * C in one instruction for C that is 1, 2 or 4 It is meant for calculating array index addresses base+index*itemsize but was found by many assembly programmers of the early days to be useful for general arithmetic. All compilers use this trick

dathinab 4y ago

sometimes I wonder if just shipping a 64bit only no legacy instructions (i.e. cleaned up x86_64) instruction set would put a stop to the ARM is fundamentally better discussion (and sure there is ARM with legacy instructions etc. but Apple silicon is 64bit no legacy cruft AFIK).

jsjohnst 4y ago
> sometimes I wonder if just shipping a 64bit only no legacy instructions (i.e. cleaned up x86_64) instruction set would put a stop to the ARM is fundamentally better discussion No > but Apple silicon is 64bit no legacy cruft AFIK No. It’s an ARMv8 ISA, legacy cruft and all.
- hajile 4y ago
  uaarch64 has very little legacy stuff left. When ARM announced A715, they got rid of uaarch32 and said it got them a 75% reduction in the size of the decoder while increasing the width of the decoder from 4 to 5-wide. They even got rid of the uop-cache because the new encoding was so much smaller and efficient that it didn't make sense to keep it around.
- dathinab 4y ago
  through its A64 only (no T32 neither A32) which cuts out a lot of legacy instructions/instruction variants. Doing the same for x86_64 would be a bit like no 16bit and 32bit specific machine instructions/instruction variants, no support for legacy bios things etc.

MichaelMoser123 4y ago

There are even more instructions: see this lecture on finding undocumented instructions https://www.youtube.com/watch?v=KrksBdWcZgQ https://www.youtube.com/watch?v=KrksBdWcZgQ

uberman 4y ago
Highly recommend watching this as it was a great presentation. Thank you for posting this