A CPU is a compiler

2023-03-22

Strictly speaking, a CPU is an interpreter; it is certainly not a compiler and, unless you can come up with a second implementation of physics, the standard tricks to turn it into one won’t work either. And yet, when comparing with software implementations of programming languages, a CPU seems closest to the back end of an optimising compiler; all sorts of duals seem to show up:

Compiler CPUNotes
Instruction scheduling Instruction scheduling
JIT Microcoding, µop cache
Branch probability analysis Branch prediction I find the contrast here particularly interesting.
Inline cache Branch target buffer
Instruction selection Fusion
Register allocation Register renaming
Coalescing Move elimination
Alias analysis Memory disambiguation
Scalar replacement of aggregates Memory renaming
Peephole optimisations, idioms Idioms For instance, a compiler might recognise a sequence for performing a rotate, byte-swap, or population count, when such functionality is supported natively by the target, but not by the source. A CPU might recognise an xor or subtraction of a register from itself as producing a zero.
Parallelising compiler, scheduler Superscalar CPU
Pipelining Pipelining, memory-level parallelism Very different types of pipelining!
Block, trace Trace

I find it somewhat irksome that we don’t refer to static register allocation and dynamic register allocation—etc.—as this would make the relationship between CPUs and compilers much clearer. Some of the ties here are admittedly too tenuous for this to really work out, but many are not.

(Update—2023-06-27—I have found a video lecture dated 1994 which refers to a compiler’s performing ‘memory disambiguation’.)

Here’s some garbage collection, as a bonus:

Garbage collector CPUNotes
Generational garbage collection QLRU cache replacement
Write barrier Snooping
Read barrier TLB lookup Particularly a use barrier.
Self-healing TLB miss/update
Forwarding pointer Page table entry
Snapshot or recolour roots TLB shootdown