Much of the code and education that resulted in this post happened with Aaron Patterson.
The fundamental problem in register allocation is to take an IR that uses a virtual registers (as many as you like) and rewrite it to use a finite amount of physical registers and stack space.
This is an example of a code snippet using virtual registers:
add R1, R2 -> R3 add R1, R3 -> R4 ret R4
And here is the same example after it has been passed through a register allocator (note that Rs changed to Ps):
add Stack[0], P0 -> P1 add Stack[0], P1 -> P0 ret
Each virtual register was assigned a physical place: R1 to the stack, R2 to P0, R3 to P1, and R4 also to P0 (since we weren’t using R2 anymore).
People use register allocators like they use garbage collectors: it’s an abstraction that can manage your resources for you, maybe with some cost. When writing the back-end of a compiler, it’s probably much easier to have a separate register-allocator-in-a-box than manually managing variable lifetimes while also considering all of your different target architectures.
How do JIT compilers do register allocation? Well, “everyone knows” that “every JIT does its own variant of linear scan”. This bothered me for some time because I’ve worked on a couple of JITs and still didn’t understand the backend bits.
There are a couple different approaches to register allocation, but in this post we’ll focus on linear scan of SSA.
... continue reading