Linear scan register allocation on SSA
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)