Modern x86 cost model

Question

I'm writing a JIT compiler with an x86 backend and learning x86 assembler and machine code as I go. I used ARM assembler about 20 years ago and am surprised by the difference in cost models between these architectures.

Specifically, memory accesses and branches are expensive on ARM but the equivalent stack operations and jumps are cheap on x86. I believe modern x86 CPUs do far more dynamic optimizations than ARM cores do and I find it difficult to anticipate their effects.

What is a good cost model to bear in mind when writing x86 assembler? Which combinations of instructions are cheap and which are expensive?

For example, my compiler would be simpler if it always generated the long form for loading integers or jumping to offsets even if the integers were small or the offsets close but would this impact performance?

I haven't done any floating point yet but I'd like to get on to it soon. Is there anything not obvious about the interaction between normal and float code?

I know there are lots of references (e.g. Michael Abrash) on x86 optimization but I have a hunch than anything more than a few years old will not apply to modern x86 CPUs because they have changed so much lately. Am I correct?

Answer 1

The best reference is the Intel Optimization Manual, which provides fairly detailed information on architectural hazards and instruction latencies for all recent Intel cores, as well as a good number of optimization examples.

Another excellent reference is Agner Fog's optimization resources, which have the virtue of also covering AMD cores.

Note that specific cost models are, by nature, micro-architecture specific. There's no such thing as an "x86 cost model" that has any kind of real validity. At the instruction level, the performance characteristics of Atom are wildly different from i7.

I would also note that memory accesses and branches are not actually "cheap" on x86 cores -- it's just that the out-of-order execution model has become so sophisticated that it can successfully hide the cost of them in many simple scenarios.

Answer 2

Torbjörn Granlund's Instruction latencies and throughput for AMD and Intel x86 processors is good too.

Edit

Granlund's document concerns instruction throughput in the context of how many instructions of a certain type can be issued per clock cycle (i e performed in parallell). He also claims that intel's documentation isn't always accurate.

Answer 3

Of course, Agner Fog's reports and the Intel® 64 and IA-32 Architectures Optimization Reference Manual are both necessary and excellent references. AMD also has an optimization manual:

• Software Optimization Guide for AMD Family 15h Processors

However, two Intel tools are essential in understanding code sequences:

• Intel® Architecture Code Analyzer
• Intel® VTune™

IACA is your cost model. I use it on OSX but VTune only runs on Windows and Linux.

You can also dig into the Intel patent literature and various Intel papers to better understand how things work:

• The Next-Generation Intel Core Microarchitecture
• Haswell: The Fourth-Generation Intel Core Processor
• Micro-operation cache: A power aware frontend for variable instruction length ISA

Answer 4

It's worth looking at the backends existing open source compilers such as GCC and LLVM. These have models for instruction costs and also decent (but idealized) machine models (eg, issue width, cache sizes, etc).

Answer 5

I'm writing a JIT compiler with an x86 backend and learning x86 assembler and machine code as I go.

The essential problem here is that a JIT compiler can't afford to spend a huge amount of time micro-optimising. Because "optimising" happens at run-time, the cost of doing optimisations needs to be less than the time saved by the optimisations (otherwise the optimisation becomes a net loss in performance).

For 80x86 there are multiple different CPUs with different behaviour/characteristics. If you take the actual CPU's specific characteristics into account, then the cost of doing the optimisation increases and you slam directly into a "costs more than you gain" barrier. This is especially true for things like "ideal instruction scheduling".

Fortunately, most (but not all) modern 80x86 CPUs have various features (out-of-order, speculative execution, hyper-threading) to mitigate (some of) the performance costs caused by "less than perfect" optimisation. This tends to make expensive optimisations less beneficial.

The first thing you're going to want to do is identify which pieces of code should be optimised and which pieces shouldn't. Things that aren't executed frequently (e.g. "only executed once" initialisation code) should not be optimised at all. It's only frequently executed pieces (e.g. inner loops, etc) where it's worth bothering. Once you've identified a piece that's worth optimising the question then becomes "how much?".

As a crude over-generalisation; I'd expect that (on average) 90% of the code isn't worth optimising at all, and for 9% of the code it's only worth doing some generic optimisation. The remaining 1% (which could benefit from extensive optimisation in theory) will end up being too much hassle for the JIT compiler developer to bother with in practice (and would result in a massive complexity/verifiability nightmare - e.g. "bugs that only exist when running on some CPUs" scenarios).