17 ms·

Does a compiler use all x86 instructions? (2010)

278 points by pepijndevos 10y ago

ajenner 10y ago
It doesn't, because there are lots of special-purpose x86 instructions that would be more trouble than they're worth to teach a compiler about. For example, instructions for accessing particular CPU features that the C and C++ languages have no concept of (cryptographic acceleration and instructions used for OS kernel code spring to mind). Some of these the compiler might know about via intrinsic functions, but won't generate for pure C/C++ code. Regarding the large number of LEA instructions in x86 code - this is actually a very useful instruction for doing several mathematical operations very compactly. You can multiply the value in a register by 1, 2, 4 or 8, add the value in another register (which can be the same one, yielding multiplication by 3, 5 or 9), add a constant value and place the result in a third register.
- Majster 10y ago
  Could you provide some links or examples? I'd love to learn more about this.
  - saynsedit 10y ago
    Just read the output of your compiler for simple functions. objdump -d, or, cc -S
    - zeusk 10y ago
      objdump -S does the trick too, it even has the C code intermixed if the -g CFLAG was used.
      - mattgodbolt 10y ago
        https://gcc.godbolt.org/ https://gcc.godbolt.org/ may help too
  - deleted 10y ago
    [deleted]
  - DSMan195276 10y ago
    For kernel/OS functions, there are lots of things that can only be done while in 'kernel-mode' with kernel privileges. These are things such as turning interrupts on and off, changing which page table is being used, changing the GDT/IDT, and other various things. C has no concept of these things, and they are very special purpose. The AES instructions are similar - C has no built-in AES functionality, and the compiler just can't figure-out in which situations it could use them. All of these instructions can be accesses through inline assembly, so you can still use them in C, the compiler just won't understand what you're doing besides "It takes in these inputs, does something, and then puts out these outputs". As for `lea`, there's nothing particularly special about it. x86 allows you to do some 'funny' addressing within instructions that take memory addresses - where you can do several calculations on the address within the instruction itself, without having to use a temporary to hold the address. `lea` just lets you 'load' the result of that calculation back into a register, presumably to let you avoid making the CPU do the calculation a bunch of times in a row. But there's nothing about `lea` that requires you to actually use addresses, rather then just plain numbers you want to shift and add. It is used a lot because `lea` is a single instruction and will generally run faster then doing a shift and some additions over multiple instructions.
- api 10y ago
  There are also AFIAK a few "deprecated" instructions that are implemented for backward compatibility but do not perform well on modern cores or have much better modern alternatives. These would be things like old MMX instructions, cruft left over from the 16-bit DOS days, etc. X86 is crufty. Of course all old architectures are crufty, and using microcode it's probably possible to keep the cruft from taking up much silicon. There are also instructions not universally available. A typical compiler will not emit these unless told to do so or unless they are coded in intrinsics or inline ASM.
  - nneonneo 10y ago
    Good examples of (essentially-deprecated) instructions include the rep prefixed instructions for string operations (modern library code for string operations typically involve a mixture of SSE, full-word loads and unrolled loops for speed); the "loop" instruction (compilers usually generate explicit loops for flexibility); pretty much all the BCD arithmetic instructions (since programming languages don't typically use BCD anymore), and many other such examples. The x86 architecture is chock-full of rarely-used legacy instructions that are mostly carried around for compatibility these days.
    - cfallin 10y ago
      > the rep prefixed instructions for string operations ... are actually preferred over a hand-written vectorized loop on Ivy Bridge and up (see [1] section 3.7.7, "Enhanced REP MOVSB and STOSB operation (ERMSB)"). It's indicated by a CPUID feature flag bit (edit: grep for "erms" in /proc/cpuinfo to see this). The reason is that microcode knows more about the dcache microachitecture, load/store units, special features (weak ordering with fence at end? [2]), etc., than you do, and can be specially optimized for the particular design. There's a slight cost to transitioning to microcode and back (to ordinary hardware-decoded instructions), of course, so for small operations it might not be a win. The section cited above shows ERMSB as ~break-even vs. 128 bit AVX on Ivy Bridge from 128 bytes up to 2KB, and about 2% faster above that. [1] Intel 64 and IA-32 Architectures Optimization Reference Manual (order #248966-026), April 2012. http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/doc/manual/64-ia-32-archite... [2] http://stackoverflow.com/questions/33480999/how-can-the-rep-stosb-instruction-execute-faster-than-the-equivalent-loop http://stackoverflow.com/questions/33480999/how-can-the-rep-...
- nneonneo 10y ago
  lea is also used frequently to actually load addresses. When passing the address of a stack buffer, for example, the compiler will usually generate code like "lea eax, [ebp-0x80]; push eax". Or, when loading the address of a struct member, you might have "lea ecx, [eax+8]".
  - praptak 10y ago
    Yup, the original intention behind lea is the & operator. Compute the address but instead of accessing the memory immediately (like mov does) just keep it for later use. Just what & does.
  - martincmartin 10y ago
    Loading an address is just adding a fixed number to the value in a register. Your two examples are mathematically equivalent to "eax = ebp - 0x80" and "ecx = eax + 8."
    - laksjd 10y ago
      Yes, but those would be two assembly instructions each. The basic idea of using lea over 'movl $ebp, $eax; addl 0x80,$eax'ist that we can shave off a cycle because lea can be executed in a single cycle. However I wonder how much any of this still matters in a time where CPUs have developed to include all sorts of complex optimizations.
      - sitkack 10y ago
        Modify the backend, or do a binary translation from one to the other and test. If `lea` is the predominate instruction, there might be microcode optimizations that favor `lea` over `movl`. My hunch is that is will be mostly the same barring overflowing the instruction cache. The microps should compile to the same instruction stream.
        rayiner 10y ago
        No, LEA issues as a single micro-op on modern Intel CPUs, but no x86 CPU will merge a sequence of shift and add into a single micro op.
- emily-c 10y ago
  lea's addressing mode arithmetic also doesn't wipe out any flags so it can be extremely useful for throwing in between arithmetic operations whose resulting flags you care about and the compare operation itself so as to obtain a greater degree of instruction level parallelism.
- webkike 10y ago
  It doesn't because when would a compiler issue syscall? Maybe if you count instructions emitted by inline assembly
  - vardump 10y ago
    Compilers do have intrinsics. No inline assembly needed for something that trivial.
- jwr 10y ago
  About LEA: adding to the above correct information, it is also useful because it can be scheduled in parallel with other ALU instructions (through a different "port" in x86 parlance), or at least that's how it used to be (I haven't looked at most recent x86 architectures). Thus compilers can use LEA to perform some arithmetic operations and generate code that will effectively run faster.
  - Tuna-Fish 10y ago
    On recent Intel CPUs, LEA is generally executed with the same resources as other arithmetic. LEAs touching 16-bit registers issue multiple micro-ops and are slow (the machine no longer has native 16-bit register support and has to mask the results in a separate op). LEAs with 1 or 2 address components are issued to port 1 or 5 and have a latency of 1, and LEAs with 3 components or a RIP-relative address are issued to port 1 exclusively, and have a latency of 3. In contrast, register-register/immediate adds and subs go to any of ports 0,1,5 or 6 and have a latency of 1, and register, immediate shifts go to ports 0 or 6 and have a latency of 1. Converting operations to LEAs really doesn't buy as much today as it used to, but a smart programmer or a compiler can occasionally grab a cycle here or there.
- column 10y ago
  is there any point in multiplying by 1 ?
  - noselasd 10y ago
    It might be used to avoid a conditional.
    - column 10y ago
      Thank you for your answer but frankly I don't understand it. Could you please elaborate?
      - noselasd 10y ago
        Generally multiplying with 1 can be used to just do (the equivalent in assembly of): a = a * b; instead of if (b != 1) a = a * b; Which is normally a win, as branching are expensive vs multiplication.
rdtsc 10y ago
> but I have no clue why there are so many lea everywhere. Pointer arithmetic? Which is used for well, ... many things.
- JoeAltmaier 10y ago
  Pointer creation I think.
  - rdtsc 10y ago
    Originally it was for address calculations it seems. But can also be used to do other calculations not just for addresses. Which I assumed to be equivalent to something like: res = ptr_base + offset
- rwmj 10y ago
  lea is used to implement addition in OCaml: http://caml.inria.fr/pub/ml-archives/caml-list/2004/07/e86a25aa6c6a6a7d08dd7eb50cfd5d52.fr.html http://caml.inria.fr/pub/ml-archives/caml-list/2004/07/e86a2...
  - dibanez 10y ago
    Yea, I've seen compilers use lea for some integer math in C/C++, because it is handled by a different part of the CPU and so can happen in parallel with other integer math ops.
    - rwmj 10y ago
      People might say this, but it's not really true. All these instructions are decomposed into micro-ops, and then the micro-ops are run in parallel - if data dependencies allow that - on a common pool of integer ALUs. The reason to use lea is for code compression - it allows you to express two or three operations in a single instruction.
      - cperciva 10y ago
rwmj 10y ago
Of course what really matters is which instructions are dynamically used the most. Can Intel performance counters collect that data? You could modify QEMU TCG mode to collect it fairly easily.
- s_kanev 10y ago
  Both static and dynamic histograms can be pretty important, actually. Dynamic ones for performance, static ones -- usually for correctness (imagine developing a tool just like QEMU, which needs to emulate each instruction type). Performance counters by themselves aren't granular enough for an exact histogram. But you can use them (especially the LBR[1] and the fancy new PT[2]) to reconstruct an approximate control-flow graph, and with a bit of post-processing it's easy to get per-instruction call frequencies. A long time ago, I wrote a paper on x86 trace compression that needed a dynamic histogram like the one you mentioned. As expected, the CDF rises very very fast [3, Fig. 5] -- you can cover a very large fraction of execution with a very small number of instructions. [1] http://lwn.net/Articles/680996/ http://lwn.net/Articles/680996/ [2] http://www.halobates.de/pt-tracing-summit15.pdf http://www.halobates.de/pt-tracing-summit15.pdf [3] http://skanev.org/papers/ispass11zcompr.pdf http://skanev.org/papers/ispass11zcompr.pdf
JoeAltmaier 10y ago
Intel's own optimizing C++ compiler uses more, or well different ones anyway. Its really amazing what it can do. Uses instructions I never heard of.
- hajile 10y ago
  Then disables any of them from running on AMD processors (and that's still the case. They were told by the courts to either place a warning or stop the practice, so they buried a vague warning in the paperwork).
Hydraulix989 10y ago
mov is Turing complete
- sytelus 10y ago
  Source?
  - misterdata 10y ago
    https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
  - tlb 10y ago
    http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
  - detaro 10y ago
    paper: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf compiler implementing it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator HN discussions of these links: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 (paper) and https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 (compiler)
  - mdadm 10y ago
    Probably things like https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
  - terminalcommand 10y ago
    Here is a paper and a mov only compiler. http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf, https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator PS: Found these links on hn.algolia.com, the HN threads are: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312
filereaper 10y ago
The point of a compiler, specifically the code-generator is to use the most effective instruction where applicable to get the job done. Its not necessary to have full coverage over the entire instruction set. Sometimes new and fancy instructions can end up being slower as opposed to using more but more standard "older" instructions to get the job done.
shanemhansen 10y ago
There are instructions that would almost never be useful. See Linus's rant on cmov http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html The tl;dr is that it would only be useful if you are trying to optimize the size of a binary.
- wscott 10y ago
  It is _very_ useful when hand optimizing loops in assembly. But for the compiler, the newer processors have such incredible branch predictors it is usually a bad idea for the compiler assume a branch is poorly predicted. Now if you are using profile guided optimizations (--prof-gen/prof-use) AND you use the processor's performance counters as part of the feedback to the compiler _then_ I could see the compiler correctly using this instruction.
  - snaky 10y ago
    I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? It looks great on microbenchmarks when there's a bunch of idle execution units to use, a memory bus and caches are underused. It may not perform so well on real load when there's no idle execution units available to use for free, and memory bus and cache lines are choking on load. Is it somewhat similar to these two examples? > If it owns that line then CAS is extremely fast - core doesn't need to notify other cores to do that operation. If core doesn't own it, the situation is very different - core has to send request to fetch cache line in exclusive mode and such request requires communication with all other cores. Such negotiation is not fast, but on Ivy Bridge it is much faster than on Nehalem. And because it is faster on Ivy Bride, core has less time to perform a set of fast local CAS operations while it owns cacheline, therefore total throughput is less. I suppose, a very good lesson learned here - microbenchmarking can be very tricky and not easy to do properly. Also results can be easily interpreted in a wrong way http://stas-blogspot.blogspot.com/2013/02/evil-of-microbenchmarking-cas.html http://stas-blogspot.blogspot.com/2013/02/evil-of-microbench... > On current processors, POPCNT runs on a single execution port and counts the bits in 4B per cycle. The AVX2 implementation requires more instructions, but spreads the work out across more ports. My fastest unrolled version takes 2.5 cycles per 32B vector, or .078 cycles/byte (2.5/32). This is 1.6x faster (4 cycles per 32B /2.5 cycles per 32B) than scalar popcnt(). Whether this is worth doing depends on the rest of the workload. If the rest of the work is being done on scalar 64-bit registers, those other scalar operations can often fit between the popcnts() "for free", and the cost of moving data back and forth between vector and scalar registers usually overwhelms the advantage. https://news.ycombinator.com/item?id=11279047 https://news.ycombinator.com/item?id=11279047
epx 10y ago
Certainly the BCD instructions are not used?
- dbcurtis 10y ago
  Well, be sure to check out a COBOL compiler before you write it off. But it's certainly rare. BCD arithmetic is an artifact of history. The 4004 was targeting desktop calculators. And IIRC all of the microprocessors in the 8008/8080 era had some support for BCD.
- dragonwriter 10y ago
  IIRC, Turbo Pascal and its descendants (including Delphi and FreePascal) have support BCD arithmetic at the language level (but it might be part of stdlib), so I'd imagine that either the compiler outputs BCD instructions or BCD instructions are inlined in the library implementation. EDIT: Although its possible that they use something else behind the scenes and just convert to/from BCD representation. That seems intuitively likely to be inefficient, but if keeping BCD ops efficient hasn't been a focus of CPU development, its possibly not the ideal way to do things under the hood, even when at the application language level it is presented as doing BCD.
- krylon 10y ago
  A couple of years back, I did a little (LITTLE! Very superficial!) research into doing BCD on x86, and if my very fuzzy memory of that time is not totally wrong, the BCD support in x86 was never all that great. Certainly nowhere near the support for arithmetic on fixed-sized binary integers. Also, being mostly unused, Intel had little incentive to to make these instructions run fast. So there might be programs somewhere that actually use these instructions, but I would not be surprised if there also were programs that do BCD arithmetic without using the x86 BCD instructions. (Especially if these were written in in a HLL, compiled by a compiler that has no idea what you are trying to do.)
kazinator 10y ago
Likely counterexample: GCC probably doesn't use AAA (ASCII Adjust after Addition). Or does it?
- to3m 10y ago
  Nobody uses AAA ;) - and by way of proof, x64 doesn't have it!
- pepijndevos 10y ago
  Not in the code on my machine at least.
chkras 10y ago
"It would be interesting to break it down further in “normal” instructions, SIMD instructions, other optimizations, and special purpose instructions… if anyone can be bothered categorizing 600+ instructions." sandpile.org Also, nop == xchg acc,acc
jcranmer 10y ago
In general: * x87 floating point is generally unused (if you have SSE2, which is guaranteed for x86-64) * BCD/ASCII instructions * BTC/BTS/related instructions. These are basically a & (1 << b) operations, but because of redundant uses, it's generally faster to do the regular operations * MMX instructions are obsoleted by SSE * There's some legacy cruft (e.g., segment management) that's generally unused by anyone not in 16-bit mode. * There are few odd instructions that are basically no-ops (LFENCE, branch predictor hints) * Several instructions are used in hand-written assembly, but won't be emitted by a compiler except perhaps by intrinsics. The AES/SHA1 instructions, system-level instructions, and several vector instructions fall into this category. * Compilers usually target relatively old instruction sets, so while they can emit vector instructions for AVX or AVX2, most shipped binaries won't by default. When you see people list minimum processor versions, what they're really listing is which minimum instruction set is being targeted (largely boiling down to "do we require SSE, SSE2, SSE3, SSSE3, SSE4.1, or SSE4.2?"). As for how many x86 instructions, there are 981 unique mnemonics and 3,684 variants (per https://stefanheule.com/papers/pldi16-strata.pdf https://stefanheule.com/papers/pldi16-strata.pdf). Note that some mnemonics mask several instructions--mov is particularly bad about that. I don't know if those counts are considered only up to AVX-2 or if they extend to the AVX-512 instruction set as well.
- dmm 10y ago
  > * There's some legacy cruft (e.g., segment management) that's generally unused by anyone not in 16-bit mode. OpenBSD uses segments(while in protected mode!) to implement a line-in-the-sand W^X implementation on i386 systems that don't support anything better. The segment is set just high enough in a processes space to cover the text and libraries but leave the heap and stack unexecutable. This mentions this implementation: http://www.tedunangst.com/flak/post/now-or-never-exec http://www.tedunangst.com/flak/post/now-or-never-exec
  - userbinator 10y ago
    VMware also uses(used?) segments to hide its hypervisor: http://www.pagetable.com/?p=25 http://www.pagetable.com/?p=25
35bge57dtjku 10y ago
> Note that the x86 was originally designed as a Pascal machine, which is why there are instructions to support nested functions (enter, leave), the pascal calling convention in which the callee pops a known number of arguments from the stack (ret K), bounds checking (bound), and so on. Many of these operations are now obsolete. http://stackoverflow.com/questions/26323215/do-any-languages-compilers-utilize-the-x86-enter-instruction-with-a-nonzero-ne http://stackoverflow.com/questions/26323215/do-any-languages...
- chkras 10y ago
  Except windows still uses stdcall which is pascal style return with c styled parameter ordering.
JosephRedfern 10y ago
Can we not look at the compiler source-code itself, rather than binaries generated by the compiler?
nixos 10y ago
My question is if compilers use "new" x86 instructions, as then the program won't work at all on old systems. For example, if Intel decided today that CPUs need a new "fast" hashing opcode (I don't know if they actually do), a compiler can't compiles to it, as programs won't work on older computers. Is it like the API cruft in Android, where "new" Lollipop APIs are introduced for 10 years from now, when no one uses any phones from before 2014?
- pjmlp 10y ago
  JIT compilers are able to take advantage of them, because you don't get a binary set in stone that has to run everywhere. This is the main reason why Apple is now pushing for LLVM bitcode, Android still uses dex even when AOT compiling and WP uses MDIL with AOT compilation at the store. So regardless of what an OEM decides for their mobile device, in theory, it is possible to make the best use of the chosen CPU. This is actually quite common in the mainframes, with AS/400 (now IBM i) being one of the most well known ones.
  - wahern 10y ago
    The AS/400 is more like an AOT than a JIT compiler. When I hear JIT I think opportunistically compiling portions of a program, but falling back to an interpreter. The way AS/400 works, IIUC, is that the compiler compiles to an intermediate byte code, which has remained stable for decades. When the program is first loaded, the entire program is compiled to the native architecture, cached, and then executed like any other binary. The reason why JIT environments aren't competitive generally with AOT compiling is because of all the instrumentation necessary. A JIT environment is usually composed of an interpreter[1] which, using various heuristics, decides to compile segments of code to native code. But the logic for deciding what segments to compile, when to reuse a cached chunk, etc is complex, especially the pieces that keep track of data dependencies. Also, each chunk requires instrumentation code for transitioning from and back into the interpreter.[2] For this and other reasons JIT'd environments aren't competitive with AOT environments except for simple programs or programs with very high code and data locality (i.e. spending most of the time inside a single compiled chunk, such as a small loop). Large or complex programs don't JIT very well. Even if the vast majority of the execution time is spent within a very small portion of the program, if data dependencies or executions paths are complex (which is usually the case) all the work spent managing the JIT'd segments can quickly add up. Programs that would JIT well also tend to be programs that vectorize well, and if they vectorize well AOT compilers also benefit and so JIT compilers are still playing catch-up. (One benefit (albeit only short term) for JIT compilers is that some performance optimizations are easier to add to JIT compilers because you don't have to worry about ABIs and other baggage; you iterate the compiler implementation faster.) I increasingly hear the term JIT used in the context of GPU programming, where programs are generated and compiled dynamically for execution on SIMD cores. But that's much more like AOT compilation. The implementation stack and code generation rules are basically identical to a traditional AOT compiler and very little like the JIT environments for Java or JavaScript. The only similarity is that compilation happens at run-time, but you can analogize that with, for example, dynamically generating, compiling, and invoking C code. Which, actually, isn't uncommon. It's how Perl's Inline::C works, and how TinyCC is often used. [1] Mike Pall has said that the secret to a fast JIT environment is a fast interpreter. [2] So, for example, calling into a module using the Lua C API is faster in PUC Lua than LuaJIT. LuaJIT has to spill more complex state, whereas the PUC Lua interpreter is just calling a C function pointer--the spilling is much simpler and has already been AOT compiled.
sklivvz1971 10y ago
The article assumes that no software in bin is written natively in asm or has asm blocks or linked objects... which seems a bit out there.
- Nacraile 10y ago
  My thought was that most binary distributions probably use very conservative configuration that will generate code that compatible with very old processors, and that you would therefore not see much use of modern instructions in /bin. This is one of the selling points of compile-yourself distributions like Arch/Gentoo: you know what processor you're running on, so you can take full advantage of its features.
  - pepijndevos 10y ago
    I'm running Ubuntu. Would be interesting to see output from a Gentoo user. [edit] Gentoo: https://bpaste.net/raw/160c1fc57842 https://bpaste.net/raw/160c1fc57842 More Gentoo: https://paste.pound-python.org/show/BOVT5z1G93GRmGGfUyQQ/ https://paste.pound-python.org/show/BOVT5z1G93GRmGGfUyQQ/
  - dyladan 10y ago
    I was under the impression that outside the AUR, Arch is primarily based on binary distribution.
- dyladan 10y ago
  That doesn't really take away from the finding though. This is obviously not meant to be a thorough analysis of what opcodes a compiler "knows" (he could have just looked at the source code for gnu cc if that were the case), but rather a quick and dirty hack showing the opcodes in actual use. Furthermore, I would assume that handwritten or inlined asm is an insignificant portion of all the opcodes in bin, making it statistically irrelevant for the pie chart. Also, handwritten asm could only add opcodes to the count of unique opcodes in bin, meaning those 200 are not only not used by the compiler, but also not used in handwritten code.
barrkel 10y ago
I extended the Borland debugger's disassembler (as used by Delphi and C++ Builder IDEs) to x64, so I had professional reason to inspect the encodings. There are whole categories of instructions not used by most compilers, relating to virtualization, multiple versions of MMX and SSE (most are rarely output by compilers), security like DRM instructions (SMX feature aka Safer Mode), diagnostics, etc. On LEA: LEA is often used to pack integer arithmetic into the ModRM and SIB prefix bytes of the address encoding, rather than needing separate instructions to express a calculation. Using these, you can specify some multiplication factors, a couple of registers and a constant all in a single bit-packed encoding scheme. Whether or not it uses different integer units in the CPU is independent of the fact that it saves code cache size.
0xdeadbeefbabe 10y ago
What's the name for a piano song that touches all the keys on the keyboard?
- user731955373 10y ago
  A diabolical suggestion with a mistake?
- mtone 10y ago
  Black MIDI (okay... it's actually a "genre", not a song, which is even worse)
deleted 10y ago
[deleted]
WalterBright 10y ago
I don't know of any that use the BCD instructions like AAA. Other instructions have been essentially obsoleted like STOSB, etc.
- kjs3 10y ago
  BCD was the one I thought of; never seen one in compiler output. I believe x86_64 completely eliminated them.
fizixer 10y ago
And therein lies the rub. What is the minimum number of instructions a compiler could make use of to get everything done that it needs? I came across an article that says 'mov is turing complete' [1]. But they had to do some convoluted tricks to use mov for all purposes. I think it's safe to say that about 5-7 instructions are all that's needed to perform all computation tasks. But then: - Why do compilers not strive to simplify their code-gen phase, or enable themselves to do advanced instruction-level program analysis, or both? - Why do microprocessors not strive for simplicity, implement only a handful of instructions in an optimized way, with a very small chip footprint, to be followed by proliferation of cores (think 256-core, 512-core, 1024-core). Besides the completely valid reason that humans tend to overly-complicate their solutions, and then brag about it, the main reason is historical baggage and the need for backwards compatibility. Intel started with a bad architecture design, and only made it worse decades after decades, by piling one bunch of instructions over another, and what we now have is a complete mess. On the compiler front, the LLVM white-knights come along and tell people 'you guys are wimps for using C to do compilers. Real men use monsters like C++, with dragons like design-patterns. No one said compiler programming is supposed to be as simple as possible.' To those lamenting javascript and the web being broken, wait till you lift the rug and get a peek at the innards of your computing platform and infrastructure! [1] https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
- fizbin 10y ago
  https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
- aschampion 10y ago
  We "over-complicate" ISAs for the same reason we're constantly adopting new vocabulary: there is efficiency in specialization. Good design is not about simplicity; it's about managed complexity. > - Why do compilers not strive to simplify their code-gen phase, or enable themselves to do advanced instruction-level program analysis, or both? Because specialized instructions formalize invariants and constraints on behavior that allow efficient computation, often by specialized hardware. > - Why do microprocessors not strive for simplicity, implement only a handful of instructions in an optimized way, with a very small chip footprint, to be followed by proliferation of cores (think 256-core, 512-core, 1024-core). Some do, see GPUs and coprocessors like the Phi. We don't take this approach with CPUs because real problems often require complex, branching, inhomogeneous computation, which require the type of specialization and tradeoffs mentioned above.
Const-me 10y ago
> It would be interesting to break it down further in “normal” instructions, SIMD instructions There’s a free disassembler library with that functionality: http://www.capstone-engine.org/ http://www.capstone-engine.org/ Here’s that break up, in its .NET wrapper library: https://github.com/9ee1/Capstone.NET/blob/master/Gee.External.Capstone/X86/X86InstructionGroup.cs https://github.com/9ee1/Capstone.NET/blob/master/Gee.Externa...
wicket 10y ago
Why does it say (2010) in the title? This article appears to have been posted today.
vorotato 10y ago
http://stackoverflow.com/questions/1658294/whats-the-purpose-of-the-lea-instruction http://stackoverflow.com/questions/1658294/whats-the-purpose...
partycoder 10y ago
Well, this is why some people like compiling their software including kernel themselves... so they can target their processor more precisely. That makes the binary less portable.
jamesabel 10y ago
FYI - the XED decoder classifies instructions https://software.intel.com/sites/landingpage/pintool/docs/65163/Xed/html/ https://software.intel.com/sites/landingpage/pintool/docs/65...
anjc 10y ago
Seems like some comments are missing the forest for the trees. The reason they're common is that it's possible to create all programs with a tiny subset of instructions. And I don't think LEAs are common due to the cool tricks you can do with them, as commented here. They're common because they're a necessary part of that tiny subset, to be used for their actual intended us...calculating and loading effective addresses, whether it's just a label or it's a 'pointer arithmetic' operation, while not affecting the status register. It seems also to have been a convention, going back 30 years in assembly, to use LEA to load addresses referenced by labels, even though a MOV will allow it and even though it's effectively the same thing.
amelius 10y ago
A more interesting question would be, imho: What new x86 instruction would a compiler benefit from most?
matrixanger 10y ago
A trivial and tiny little bit improvement: `objdump -d /usr/bin/* | cut -f3 | grep -oE "^[a-z]+" | sort | uniq -c | sort -k -1rn | head -n5` to get the top-5 instructions.

278 points by pepijndevos 10y ago

It doesn't, because there are lots of special-purpose x86 instructions that would be more trouble than they're worth to teach a compiler about. For example, instructions for accessing particular CPU features that the C and C++ languages have no concept of (cryptographic acceleration and instructions used for OS kernel code spring to mind). Some of these the compiler might know about via intrinsic functions, but won't generate for pure C/C++ code. Regarding the large number of LEA instructions in x86 code - this is actually a very useful instruction for doing several mathematical operations very compactly. You can multiply the value in a register by 1, 2, 4 or 8, add the value in another register (which can be the same one, yielding multiplication by 3, 5 or 9), add a constant value and place the result in a third register.

Majster 10y ago
Could you provide some links or examples? I'd love to learn more about this.
- saynsedit 10y ago
  Just read the output of your compiler for simple functions. objdump -d, or, cc -S
  - zeusk 10y ago
    objdump -S does the trick too, it even has the C code intermixed if the -g CFLAG was used.
    - mattgodbolt 10y ago
      https://gcc.godbolt.org/ https://gcc.godbolt.org/ may help too
- deleted 10y ago
  [deleted]
- DSMan195276 10y ago
  For kernel/OS functions, there are lots of things that can only be done while in 'kernel-mode' with kernel privileges. These are things such as turning interrupts on and off, changing which page table is being used, changing the GDT/IDT, and other various things. C has no concept of these things, and they are very special purpose. The AES instructions are similar - C has no built-in AES functionality, and the compiler just can't figure-out in which situations it could use them. All of these instructions can be accesses through inline assembly, so you can still use them in C, the compiler just won't understand what you're doing besides "It takes in these inputs, does something, and then puts out these outputs". As for `lea`, there's nothing particularly special about it. x86 allows you to do some 'funny' addressing within instructions that take memory addresses - where you can do several calculations on the address within the instruction itself, without having to use a temporary to hold the address. `lea` just lets you 'load' the result of that calculation back into a register, presumably to let you avoid making the CPU do the calculation a bunch of times in a row. But there's nothing about `lea` that requires you to actually use addresses, rather then just plain numbers you want to shift and add. It is used a lot because `lea` is a single instruction and will generally run faster then doing a shift and some additions over multiple instructions.
api 10y ago
There are also AFIAK a few "deprecated" instructions that are implemented for backward compatibility but do not perform well on modern cores or have much better modern alternatives. These would be things like old MMX instructions, cruft left over from the 16-bit DOS days, etc. X86 is crufty. Of course all old architectures are crufty, and using microcode it's probably possible to keep the cruft from taking up much silicon. There are also instructions not universally available. A typical compiler will not emit these unless told to do so or unless they are coded in intrinsics or inline ASM.
- nneonneo 10y ago
  Good examples of (essentially-deprecated) instructions include the rep prefixed instructions for string operations (modern library code for string operations typically involve a mixture of SSE, full-word loads and unrolled loops for speed); the "loop" instruction (compilers usually generate explicit loops for flexibility); pretty much all the BCD arithmetic instructions (since programming languages don't typically use BCD anymore), and many other such examples. The x86 architecture is chock-full of rarely-used legacy instructions that are mostly carried around for compatibility these days.
  - cfallin 10y ago
    > the rep prefixed instructions for string operations ... are actually preferred over a hand-written vectorized loop on Ivy Bridge and up (see [1] section 3.7.7, "Enhanced REP MOVSB and STOSB operation (ERMSB)"). It's indicated by a CPUID feature flag bit (edit: grep for "erms" in /proc/cpuinfo to see this). The reason is that microcode knows more about the dcache microachitecture, load/store units, special features (weak ordering with fence at end? [2]), etc., than you do, and can be specially optimized for the particular design. There's a slight cost to transitioning to microcode and back (to ordinary hardware-decoded instructions), of course, so for small operations it might not be a win. The section cited above shows ERMSB as ~break-even vs. 128 bit AVX on Ivy Bridge from 128 bytes up to 2KB, and about 2% faster above that. [1] Intel 64 and IA-32 Architectures Optimization Reference Manual (order #248966-026), April 2012. http://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf http://www.intel.com/content/dam/doc/manual/64-ia-32-archite... [2] http://stackoverflow.com/questions/33480999/how-can-the-rep-stosb-instruction-execute-faster-than-the-equivalent-loop http://stackoverflow.com/questions/33480999/how-can-the-rep-...
nneonneo 10y ago
lea is also used frequently to actually load addresses. When passing the address of a stack buffer, for example, the compiler will usually generate code like "lea eax, [ebp-0x80]; push eax". Or, when loading the address of a struct member, you might have "lea ecx, [eax+8]".
- praptak 10y ago
  Yup, the original intention behind lea is the & operator. Compute the address but instead of accessing the memory immediately (like mov does) just keep it for later use. Just what & does.
- martincmartin 10y ago
  Loading an address is just adding a fixed number to the value in a register. Your two examples are mathematically equivalent to "eax = ebp - 0x80" and "ecx = eax + 8."
  - laksjd 10y ago
    Yes, but those would be two assembly instructions each. The basic idea of using lea over 'movl $ebp, $eax; addl 0x80,$eax'ist that we can shave off a cycle because lea can be executed in a single cycle. However I wonder how much any of this still matters in a time where CPUs have developed to include all sorts of complex optimizations.
    - sitkack 10y ago
      Modify the backend, or do a binary translation from one to the other and test. If `lea` is the predominate instruction, there might be microcode optimizations that favor `lea` over `movl`. My hunch is that is will be mostly the same barring overflowing the instruction cache. The microps should compile to the same instruction stream.
      - rayiner 10y ago
        No, LEA issues as a single micro-op on modern Intel CPUs, but no x86 CPU will merge a sequence of shift and add into a single micro op.
emily-c 10y ago
lea's addressing mode arithmetic also doesn't wipe out any flags so it can be extremely useful for throwing in between arithmetic operations whose resulting flags you care about and the compare operation itself so as to obtain a greater degree of instruction level parallelism.
webkike 10y ago
It doesn't because when would a compiler issue syscall? Maybe if you count instructions emitted by inline assembly
- vardump 10y ago
  Compilers do have intrinsics. No inline assembly needed for something that trivial.
jwr 10y ago
About LEA: adding to the above correct information, it is also useful because it can be scheduled in parallel with other ALU instructions (through a different "port" in x86 parlance), or at least that's how it used to be (I haven't looked at most recent x86 architectures). Thus compilers can use LEA to perform some arithmetic operations and generate code that will effectively run faster.
- Tuna-Fish 10y ago
  On recent Intel CPUs, LEA is generally executed with the same resources as other arithmetic. LEAs touching 16-bit registers issue multiple micro-ops and are slow (the machine no longer has native 16-bit register support and has to mask the results in a separate op). LEAs with 1 or 2 address components are issued to port 1 or 5 and have a latency of 1, and LEAs with 3 components or a RIP-relative address are issued to port 1 exclusively, and have a latency of 3. In contrast, register-register/immediate adds and subs go to any of ports 0,1,5 or 6 and have a latency of 1, and register, immediate shifts go to ports 0 or 6 and have a latency of 1. Converting operations to LEAs really doesn't buy as much today as it used to, but a smart programmer or a compiler can occasionally grab a cycle here or there.
column 10y ago
is there any point in multiplying by 1 ?
- noselasd 10y ago
  It might be used to avoid a conditional.
  - column 10y ago
    Thank you for your answer but frankly I don't understand it. Could you please elaborate?
    - noselasd 10y ago
      Generally multiplying with 1 can be used to just do (the equivalent in assembly of): a = a * b; instead of if (b != 1) a = a * b; Which is normally a win, as branching are expensive vs multiplication.

rdtsc 10y ago

> but I have no clue why there are so many lea everywhere. Pointer arithmetic? Which is used for well, ... many things.

JoeAltmaier 10y ago
Pointer creation I think.
- rdtsc 10y ago
  Originally it was for address calculations it seems. But can also be used to do other calculations not just for addresses. Which I assumed to be equivalent to something like: res = ptr_base + offset
rwmj 10y ago
lea is used to implement addition in OCaml: http://caml.inria.fr/pub/ml-archives/caml-list/2004/07/e86a25aa6c6a6a7d08dd7eb50cfd5d52.fr.html http://caml.inria.fr/pub/ml-archives/caml-list/2004/07/e86a2...
- dibanez 10y ago
  Yea, I've seen compilers use lea for some integer math in C/C++, because it is handled by a different part of the CPU and so can happen in parallel with other integer math ops.
  - rwmj 10y ago
    People might say this, but it's not really true. All these instructions are decomposed into micro-ops, and then the micro-ops are run in parallel - if data dependencies allow that - on a common pool of integer ALUs. The reason to use lea is for code compression - it allows you to express two or three operations in a single instruction.
    - cperciva 10y ago

rwmj 10y ago

Of course what really matters is which instructions are dynamically used the most. Can Intel performance counters collect that data? You could modify QEMU TCG mode to collect it fairly easily.

s_kanev 10y ago
Both static and dynamic histograms can be pretty important, actually. Dynamic ones for performance, static ones -- usually for correctness (imagine developing a tool just like QEMU, which needs to emulate each instruction type). Performance counters by themselves aren't granular enough for an exact histogram. But you can use them (especially the LBR[1] and the fancy new PT[2]) to reconstruct an approximate control-flow graph, and with a bit of post-processing it's easy to get per-instruction call frequencies. A long time ago, I wrote a paper on x86 trace compression that needed a dynamic histogram like the one you mentioned. As expected, the CDF rises very very fast [3, Fig. 5] -- you can cover a very large fraction of execution with a very small number of instructions. [1] http://lwn.net/Articles/680996/ http://lwn.net/Articles/680996/ [2] http://www.halobates.de/pt-tracing-summit15.pdf http://www.halobates.de/pt-tracing-summit15.pdf [3] http://skanev.org/papers/ispass11zcompr.pdf http://skanev.org/papers/ispass11zcompr.pdf

JoeAltmaier 10y ago

Intel's own optimizing C++ compiler uses more, or well different ones anyway. Its really amazing what it can do. Uses instructions I never heard of.

hajile 10y ago
Then disables any of them from running on AMD processors (and that's still the case. They were told by the courts to either place a warning or stop the practice, so they buried a vague warning in the paperwork).

Hydraulix989 10y ago

mov is Turing complete

sytelus 10y ago
Source?
- misterdata 10y ago
  https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- tlb 10y ago
  http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
- detaro 10y ago
  paper: https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf compiler implementing it: https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator HN discussions of these links: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 (paper) and https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312 (compiler)
- mdadm 10y ago
  Probably things like https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator
- terminalcommand 10y ago
  Here is a paper and a mov only compiler. http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf, https://github.com/xoreaxeaxeax/movfuscator https://github.com/xoreaxeaxeax/movfuscator PS: Found these links on hn.algolia.com, the HN threads are: https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=6309631 https://news.ycombinator.com/item?id=9751312 https://news.ycombinator.com/item?id=9751312

filereaper 10y ago

The point of a compiler, specifically the code-generator is to use the most effective instruction where applicable to get the job done. Its not necessary to have full coverage over the entire instruction set. Sometimes new and fancy instructions can end up being slower as opposed to using more but more standard "older" instructions to get the job done.

shanemhansen 10y ago

There are instructions that would almost never be useful. See Linus's rant on cmov http://yarchive.net/comp/linux/cmov.html http://yarchive.net/comp/linux/cmov.html The tl;dr is that it would only be useful if you are trying to optimize the size of a binary.

wscott 10y ago
It is _very_ useful when hand optimizing loops in assembly. But for the compiler, the newer processors have such incredible branch predictors it is usually a bad idea for the compiler assume a branch is poorly predicted. Now if you are using profile guided optimizations (--prof-gen/prof-use) AND you use the processor's performance counters as part of the feedback to the compiler _then_ I could see the compiler correctly using this instruction.
- snaky 10y ago
  I have a mixed feeling about that incredible progress in modern CPUs branch prediction. Don't they just use idle execution units and run both branches in parallel behind the scenes? It looks great on microbenchmarks when there's a bunch of idle execution units to use, a memory bus and caches are underused. It may not perform so well on real load when there's no idle execution units available to use for free, and memory bus and cache lines are choking on load. Is it somewhat similar to these two examples? > If it owns that line then CAS is extremely fast - core doesn't need to notify other cores to do that operation. If core doesn't own it, the situation is very different - core has to send request to fetch cache line in exclusive mode and such request requires communication with all other cores. Such negotiation is not fast, but on Ivy Bridge it is much faster than on Nehalem. And because it is faster on Ivy Bride, core has less time to perform a set of fast local CAS operations while it owns cacheline, therefore total throughput is less. I suppose, a very good lesson learned here - microbenchmarking can be very tricky and not easy to do properly. Also results can be easily interpreted in a wrong way http://stas-blogspot.blogspot.com/2013/02/evil-of-microbenchmarking-cas.html http://stas-blogspot.blogspot.com/2013/02/evil-of-microbench... > On current processors, POPCNT runs on a single execution port and counts the bits in 4B per cycle. The AVX2 implementation requires more instructions, but spreads the work out across more ports. My fastest unrolled version takes 2.5 cycles per 32B vector, or .078 cycles/byte (2.5/32). This is 1.6x faster (4 cycles per 32B /2.5 cycles per 32B) than scalar popcnt(). Whether this is worth doing depends on the rest of the workload. If the rest of the work is being done on scalar 64-bit registers, those other scalar operations can often fit between the popcnts() "for free", and the cost of moving data back and forth between vector and scalar registers usually overwhelms the advantage. https://news.ycombinator.com/item?id=11279047 https://news.ycombinator.com/item?id=11279047

epx 10y ago

Certainly the BCD instructions are not used?

dbcurtis 10y ago
Well, be sure to check out a COBOL compiler before you write it off. But it's certainly rare. BCD arithmetic is an artifact of history. The 4004 was targeting desktop calculators. And IIRC all of the microprocessors in the 8008/8080 era had some support for BCD.
dragonwriter 10y ago
IIRC, Turbo Pascal and its descendants (including Delphi and FreePascal) have support BCD arithmetic at the language level (but it might be part of stdlib), so I'd imagine that either the compiler outputs BCD instructions or BCD instructions are inlined in the library implementation. EDIT: Although its possible that they use something else behind the scenes and just convert to/from BCD representation. That seems intuitively likely to be inefficient, but if keeping BCD ops efficient hasn't been a focus of CPU development, its possibly not the ideal way to do things under the hood, even when at the application language level it is presented as doing BCD.
krylon 10y ago
A couple of years back, I did a little (LITTLE! Very superficial!) research into doing BCD on x86, and if my very fuzzy memory of that time is not totally wrong, the BCD support in x86 was never all that great. Certainly nowhere near the support for arithmetic on fixed-sized binary integers. Also, being mostly unused, Intel had little incentive to to make these instructions run fast. So there might be programs somewhere that actually use these instructions, but I would not be surprised if there also were programs that do BCD arithmetic without using the x86 BCD instructions. (Especially if these were written in in a HLL, compiled by a compiler that has no idea what you are trying to do.)

kazinator 10y ago

Likely counterexample: GCC probably doesn't use AAA (ASCII Adjust after Addition). Or does it?

to3m 10y ago
Nobody uses AAA ;) - and by way of proof, x64 doesn't have it!
pepijndevos 10y ago
Not in the code on my machine at least.

chkras 10y ago

"It would be interesting to break it down further in “normal” instructions, SIMD instructions, other optimizations, and special purpose instructions… if anyone can be bothered categorizing 600+ instructions." sandpile.org Also, nop == xchg acc,acc

jcranmer 10y ago

In general: * x87 floating point is generally unused (if you have SSE2, which is guaranteed for x86-64) * BCD/ASCII instructions * BTC/BTS/related instructions. These are basically a & (1 << b) operations, but because of redundant uses, it's generally faster to do the regular operations * MMX instructions are obsoleted by SSE * There's some legacy cruft (e.g., segment management) that's generally unused by anyone not in 16-bit mode. * There are few odd instructions that are basically no-ops (LFENCE, branch predictor hints) * Several instructions are used in hand-written assembly, but won't be emitted by a compiler except perhaps by intrinsics. The AES/SHA1 instructions, system-level instructions, and several vector instructions fall into this category. * Compilers usually target relatively old instruction sets, so while they can emit vector instructions for AVX or AVX2, most shipped binaries won't by default. When you see people list minimum processor versions, what they're really listing is which minimum instruction set is being targeted (largely boiling down to "do we require SSE, SSE2, SSE3, SSSE3, SSE4.1, or SSE4.2?"). As for how many x86 instructions, there are 981 unique mnemonics and 3,684 variants (per https://stefanheule.com/papers/pldi16-strata.pdf https://stefanheule.com/papers/pldi16-strata.pdf). Note that some mnemonics mask several instructions--mov is particularly bad about that. I don't know if those counts are considered only up to AVX-2 or if they extend to the AVX-512 instruction set as well.

dmm 10y ago
> * There's some legacy cruft (e.g., segment management) that's generally unused by anyone not in 16-bit mode. OpenBSD uses segments(while in protected mode!) to implement a line-in-the-sand W^X implementation on i386 systems that don't support anything better. The segment is set just high enough in a processes space to cover the text and libraries but leave the heap and stack unexecutable. This mentions this implementation: http://www.tedunangst.com/flak/post/now-or-never-exec http://www.tedunangst.com/flak/post/now-or-never-exec
- userbinator 10y ago
  VMware also uses(used?) segments to hide its hypervisor: http://www.pagetable.com/?p=25 http://www.pagetable.com/?p=25

35bge57dtjku 10y ago

> Note that the x86 was originally designed as a Pascal machine, which is why there are instructions to support nested functions (enter, leave), the pascal calling convention in which the callee pops a known number of arguments from the stack (ret K), bounds checking (bound), and so on. Many of these operations are now obsolete. http://stackoverflow.com/questions/26323215/do-any-languages-compilers-utilize-the-x86-enter-instruction-with-a-nonzero-ne http://stackoverflow.com/questions/26323215/do-any-languages...

chkras 10y ago
Except windows still uses stdcall which is pascal style return with c styled parameter ordering.

JosephRedfern 10y ago

Can we not look at the compiler source-code itself, rather than binaries generated by the compiler?

nixos 10y ago

My question is if compilers use "new" x86 instructions, as then the program won't work at all on old systems. For example, if Intel decided today that CPUs need a new "fast" hashing opcode (I don't know if they actually do), a compiler can't compiles to it, as programs won't work on older computers. Is it like the API cruft in Android, where "new" Lollipop APIs are introduced for 10 years from now, when no one uses any phones from before 2014?

pjmlp 10y ago
JIT compilers are able to take advantage of them, because you don't get a binary set in stone that has to run everywhere. This is the main reason why Apple is now pushing for LLVM bitcode, Android still uses dex even when AOT compiling and WP uses MDIL with AOT compilation at the store. So regardless of what an OEM decides for their mobile device, in theory, it is possible to make the best use of the chosen CPU. This is actually quite common in the mainframes, with AS/400 (now IBM i) being one of the most well known ones.
- wahern 10y ago
  The AS/400 is more like an AOT than a JIT compiler. When I hear JIT I think opportunistically compiling portions of a program, but falling back to an interpreter. The way AS/400 works, IIUC, is that the compiler compiles to an intermediate byte code, which has remained stable for decades. When the program is first loaded, the entire program is compiled to the native architecture, cached, and then executed like any other binary. The reason why JIT environments aren't competitive generally with AOT compiling is because of all the instrumentation necessary. A JIT environment is usually composed of an interpreter[1] which, using various heuristics, decides to compile segments of code to native code. But the logic for deciding what segments to compile, when to reuse a cached chunk, etc is complex, especially the pieces that keep track of data dependencies. Also, each chunk requires instrumentation code for transitioning from and back into the interpreter.[2] For this and other reasons JIT'd environments aren't competitive with AOT environments except for simple programs or programs with very high code and data locality (i.e. spending most of the time inside a single compiled chunk, such as a small loop). Large or complex programs don't JIT very well. Even if the vast majority of the execution time is spent within a very small portion of the program, if data dependencies or executions paths are complex (which is usually the case) all the work spent managing the JIT'd segments can quickly add up. Programs that would JIT well also tend to be programs that vectorize well, and if they vectorize well AOT compilers also benefit and so JIT compilers are still playing catch-up. (One benefit (albeit only short term) for JIT compilers is that some performance optimizations are easier to add to JIT compilers because you don't have to worry about ABIs and other baggage; you iterate the compiler implementation faster.) I increasingly hear the term JIT used in the context of GPU programming, where programs are generated and compiled dynamically for execution on SIMD cores. But that's much more like AOT compilation. The implementation stack and code generation rules are basically identical to a traditional AOT compiler and very little like the JIT environments for Java or JavaScript. The only similarity is that compilation happens at run-time, but you can analogize that with, for example, dynamically generating, compiling, and invoking C code. Which, actually, isn't uncommon. It's how Perl's Inline::C works, and how TinyCC is often used. [1] Mike Pall has said that the secret to a fast JIT environment is a fast interpreter. [2] So, for example, calling into a module using the Lua C API is faster in PUC Lua than LuaJIT. LuaJIT has to spill more complex state, whereas the PUC Lua interpreter is just calling a C function pointer--the spilling is much simpler and has already been AOT compiled.

sklivvz1971 10y ago

The article assumes that no software in bin is written natively in asm or has asm blocks or linked objects... which seems a bit out there.

Nacraile 10y ago
My thought was that most binary distributions probably use very conservative configuration that will generate code that compatible with very old processors, and that you would therefore not see much use of modern instructions in /bin. This is one of the selling points of compile-yourself distributions like Arch/Gentoo: you know what processor you're running on, so you can take full advantage of its features.
- pepijndevos 10y ago
  I'm running Ubuntu. Would be interesting to see output from a Gentoo user. [edit] Gentoo: https://bpaste.net/raw/160c1fc57842 https://bpaste.net/raw/160c1fc57842 More Gentoo: https://paste.pound-python.org/show/BOVT5z1G93GRmGGfUyQQ/ https://paste.pound-python.org/show/BOVT5z1G93GRmGGfUyQQ/
- dyladan 10y ago
  I was under the impression that outside the AUR, Arch is primarily based on binary distribution.
dyladan 10y ago
That doesn't really take away from the finding though. This is obviously not meant to be a thorough analysis of what opcodes a compiler "knows" (he could have just looked at the source code for gnu cc if that were the case), but rather a quick and dirty hack showing the opcodes in actual use. Furthermore, I would assume that handwritten or inlined asm is an insignificant portion of all the opcodes in bin, making it statistically irrelevant for the pie chart. Also, handwritten asm could only add opcodes to the count of unique opcodes in bin, meaning those 200 are not only not used by the compiler, but also not used in handwritten code.

barrkel 10y ago

I extended the Borland debugger's disassembler (as used by Delphi and C++ Builder IDEs) to x64, so I had professional reason to inspect the encodings. There are whole categories of instructions not used by most compilers, relating to virtualization, multiple versions of MMX and SSE (most are rarely output by compilers), security like DRM instructions (SMX feature aka Safer Mode), diagnostics, etc. On LEA: LEA is often used to pack integer arithmetic into the ModRM and SIB prefix bytes of the address encoding, rather than needing separate instructions to express a calculation. Using these, you can specify some multiplication factors, a couple of registers and a constant all in a single bit-packed encoding scheme. Whether or not it uses different integer units in the CPU is independent of the fact that it saves code cache size.

0xdeadbeefbabe 10y ago

What's the name for a piano song that touches all the keys on the keyboard?

user731955373 10y ago
A diabolical suggestion with a mistake?
mtone 10y ago
Black MIDI (okay... it's actually a "genre", not a song, which is even worse)

deleted 10y ago

[deleted]

WalterBright 10y ago

I don't know of any that use the BCD instructions like AAA. Other instructions have been essentially obsoleted like STOSB, etc.

kjs3 10y ago
BCD was the one I thought of; never seen one in compiler output. I believe x86_64 completely eliminated them.

fizixer 10y ago

And therein lies the rub. What is the minimum number of instructions a compiler could make use of to get everything done that it needs? I came across an article that says 'mov is turing complete' [1]. But they had to do some convoluted tricks to use mov for all purposes. I think it's safe to say that about 5-7 instructions are all that's needed to perform all computation tasks. But then: - Why do compilers not strive to simplify their code-gen phase, or enable themselves to do advanced instruction-level program analysis, or both? - Why do microprocessors not strive for simplicity, implement only a handful of instructions in an optimized way, with a very small chip footprint, to be followed by proliferation of cores (think 256-core, 512-core, 1024-core). Besides the completely valid reason that humans tend to overly-complicate their solutions, and then brag about it, the main reason is historical baggage and the need for backwards compatibility. Intel started with a bad architecture design, and only made it worse decades after decades, by piling one bunch of instructions over another, and what we now have is a complete mess. On the compiler front, the LLVM white-knights come along and tell people 'you guys are wimps for using C to do compilers. Real men use monsters like C++, with dragons like design-patterns. No one said compiler programming is supposed to be as simple as possible.' To those lamenting javascript and the web being broken, wait till you lift the rug and get a peek at the innards of your computing platform and infrastructure! [1] https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf

fizbin 10y ago
https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer
aschampion 10y ago
We "over-complicate" ISAs for the same reason we're constantly adopting new vocabulary: there is efficiency in specialization. Good design is not about simplicity; it's about managed complexity. > - Why do compilers not strive to simplify their code-gen phase, or enable themselves to do advanced instruction-level program analysis, or both? Because specialized instructions formalize invariants and constraints on behavior that allow efficient computation, often by specialized hardware. > - Why do microprocessors not strive for simplicity, implement only a handful of instructions in an optimized way, with a very small chip footprint, to be followed by proliferation of cores (think 256-core, 512-core, 1024-core). Some do, see GPUs and coprocessors like the Phi. We don't take this approach with CPUs because real problems often require complex, branching, inhomogeneous computation, which require the type of specialization and tradeoffs mentioned above.

Const-me 10y ago

> It would be interesting to break it down further in “normal” instructions, SIMD instructions There’s a free disassembler library with that functionality: http://www.capstone-engine.org/ http://www.capstone-engine.org/ Here’s that break up, in its .NET wrapper library: https://github.com/9ee1/Capstone.NET/blob/master/Gee.External.Capstone/X86/X86InstructionGroup.cs https://github.com/9ee1/Capstone.NET/blob/master/Gee.Externa...

wicket 10y ago

Why does it say (2010) in the title? This article appears to have been posted today.

vorotato 10y ago

http://stackoverflow.com/questions/1658294/whats-the-purpose-of-the-lea-instruction http://stackoverflow.com/questions/1658294/whats-the-purpose...

partycoder 10y ago

Well, this is why some people like compiling their software including kernel themselves... so they can target their processor more precisely. That makes the binary less portable.

jamesabel 10y ago

FYI - the XED decoder classifies instructions https://software.intel.com/sites/landingpage/pintool/docs/65163/Xed/html/ https://software.intel.com/sites/landingpage/pintool/docs/65...

anjc 10y ago

Seems like some comments are missing the forest for the trees. The reason they're common is that it's possible to create all programs with a tiny subset of instructions. And I don't think LEAs are common due to the cool tricks you can do with them, as commented here. They're common because they're a necessary part of that tiny subset, to be used for their actual intended us...calculating and loading effective addresses, whether it's just a label or it's a 'pointer arithmetic' operation, while not affecting the status register. It seems also to have been a convention, going back 30 years in assembly, to use LEA to load addresses referenced by labels, even though a MOV will allow it and even though it's effectively the same thing.

amelius 10y ago

A more interesting question would be, imho: What new x86 instruction would a compiler benefit from most?

matrixanger 10y ago

A trivial and tiny little bit improvement: `objdump -d /usr/bin/* | cut -f3 | grep -oE "^[a-z]+" | sort | uniq -c | sort -k -1rn | head -n5` to get the top-5 instructions.