Does a compiler use all x86 instructions? (2010)

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.

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

x86 NaCl uses segments for sandboxing.

Would Intel be able to meet the smaller die sizes they're currently having trouble with? Would it make the processors any less expensive to produce at scale (all other things equal)?

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

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

What you're describing is a GPU--revert a core to a basic ALU and make it be 2 dozen 16-wide SIMD ALUs. Not everything can work well on a GPU, though; you need very high parallelizibility, and fairly uniform memory access models. It's why supercomputers switched from SIMD to MIMD models a few decades ago. (They're starting to revert to include more GPU-like cores, mostly for power reasons).

Modern CPU designers have such a larger transistor budget than they need to get creative to make use of all of it, so specialized instructions are pretty much free.

And no, you can't just stuff 1024 cores in a processor; apart from the fact that most software wouldn't know what to make of it, such a monster might end up bottlenecked by intercommunication or memory bandwidth.

Also simple CPUs are just slow; you need a lot of machinery to perform well at high frequency/high memory latency.

I didn't go for the absolute minimum, but I did aim for useful and reasonable minimum with the ggx[1] ISA (now called moxie[1]) by defining the ISA incrementally and only adding instructions used by GCC.

The approach I took is described here: [1] https://github.com/atgreen/ggx

[2] http://moxielogic.org/

Because that would not make CPUs faster or cheaper.

If you think that modern CPUs are large because they implement a lot of instructions, you are completely wrong. The entire machinery needed for executing more than a couple of different instructions is less than 1% of the core. The space is not taken up by decoding tables or ALUs, it's taken up by forwarding networks, registers, and most of all, cache. And all of those are things very much required to make a CPU fast. CPUs have a lot of instructions precisely because the cost of implementing a new instruction is negligible compared to the size of the CPU.

I think it's safe to say that about 5-7 instructions are all that's needed to perform all computation tasks.

One instruction is needed to be Turing-complete. It's not very practical though, as you need many more simple instructions to do the work of a single complex one.

Consider memcpy(), one of my favourite examples. On a simple architecture like MIPS, the software has to explicitly perform each read and write along with updating the pointers, the address calculations, and the loop control. It also has to take into account alignment and when to use byte/word/dword accesses. This all requires instructions, which occupy precious cache space (and unrolling makes them take even more) and have to be fetched, decoded, and executed. It can only read and write e.g. 32 bits at a time, because that's the only size the architecture supports for individual load and store instructions. If a wider (e.g. 64 bit) revision appears, all existing memcpy() has to be rewritten to take advantage of it.

On the other hand, consider the CISC solution: REP MOVSB. A single two-byte instruction which the hardware decodes into whatever operations are most optimised for it. It handles updating the registers, the copy, and the loop using specialised hardware. It can transfer entire cache lines (64 bytes or more) per clock cycle. Software doesn't need to change to take advantage of e.g. a newer processor with a wider memory bus. It's tiny, so it uses next to no cache space, and once it's been fetched, decoded, and executing internally, the memory/cache buses are free for other purposes like transferring the data to be copied, or for the other cores to use. It's far easier for the CPU to decode a complex instruction internally into micro-ops and/or dispatch it to dedicated hardware than it is to try pattern-matching long sequences of simple instructions into a complex semantic unit for such hardware when it becomes available. It's hard enough for something as simple as memcpy(), never mind AES or SHA1.

- Why do compilers not strive to simplify their code-gen phase, or enable themselves to do advanced instruction-level program analysis, or both?

Compilers are complex because the CPUs they generate code for are also complex, and the CPUs are complex because of the reason above: this complexity is efficency. A compiler for a simple CPU could be simple, but that just means the CPU is so simple that there is nothing to optimise at the software level; hardly an ideal situation. I think it wouldn't be too hard to get GCC to generate only the subset of x86 instructions that most closely resembles MIPS, and compare the resulting binaries for size and speed. It should then be obvious why more complex instructions are good.

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.

For example, you could have a function

    void hash(char *out, const char *in);

    void fast_hash(char *out, const char *in);
    void slow_hash(char *out, const char *in);

    void (*resolve_hasher(void))(char *, const char *)
    {
        if (cpuSupportsFancyInstructions()) {
            return &fast_hash;
        } else {
            return &slow_hash;
        }
    }

For handcoded assembly, it's not uncommon for code to check a CPU's capabilities at runtime (e.g. OpenSSL checks at runtime if it can use the really fast AES-NI instructions,. If not, it fall backs to other assembly or C implementations). That way you don't need different binaries tuned for every possible combination of available instructions. I don't think any compilers do this automatically, but most of the time generating assembly for the lowest common denominator is fast enough.

We have in the past received different binaries from vendors to use depending on which processors we're using.

Another alternative is to use the new instructions regardless, then trap illegal instructions and emulate them. This used to be a common way to handle floating point instructions, back in the days when FPU hardware wasn't universal. CPUs with FPUs would run the instructions natively, and CPUs without them would emulate them in software. This was, of course, unbelievably slow, but it worked.

But for the most part, you just generate different code for different CPU capabilities and dispatch, as the other comments describe.

Gentoo linux uses this to slightly optimize binaries - because every gentoo user specifies these flags systemwide, customizes them for herhis cpu, and the whole system is recompiled taking them into account. Performance boost is negligible from my experience (but I used gentoo 10 years ago, maybe it changed).

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.

What's maybe more curious, some instructions in certain modes aren't even implemented by some assemblers. I don't think it's entirely unusual to see hand crafted opcodes in an OS boot sequence. When the assembler doesn't do it, the compiler certainly isn't going to.

Then the compiler works hard on determining if branches are highly predictable. Is the branch part of closing a loop? Predict that you will stay in the loop. Is the branch checking for an exception condition? Predict that the exception is rare. OTOH, there are some branches that are, in fact, "flakey" on a dynamic execution basis. Deciding where to push a particular particle of data based on it's value inside an innermost processing loop, for instance.

So... the compiler identifies "flakey" branches, it emits code to compute both branches of the if, and CMOVs the desired result at the end. That allows the instruction issue pipeline to avoid seeing a branch at all, thus avoiding polluting the branch cache with a flakey branch, and avoiding a whole bunch of pipeline flushes in the back end. At the cost of using extra back-end resources on throw-away work.

CMOV is in X86 for a reason. On Pentium Pro and later, it is a win if your compiler has good branch analysis.

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/ [2] http://www.halobates.de/pt-tracing-summit15.pdf [3] http://skanev.org/papers/ispass11zcompr.pdf

So if you write:

    a = 4 * b + c + 10;

    lea    0xa(%rsi,%rdi,4),%rax

    imul   $0x4,%rdi,%rax
    add    %rsi,%rax
    add    $0xa,%rax

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.

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.

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