The problem of register allocation
This is a very broad subject. The problem of deciding how to map a program with arbitrarily many variables onto a fixed set of registers is known as register allocation, and it has been the subject of much research, study, and engineering effort since the very earliest compilers. One of the canonical approaches, graph coloring, was first proposed in 1981. Countless other approaches and variants have been explored since then, and I cannot hope to cover the full breadth of the topic in a single answer.
Instead, I will try to give a general overview of the problem viewed through the perspective of a compiler developer. In your question, you write
What heuristics/tests do [compilers] use to determine [which variable] should go into a register?
But this is sort of the wrong question to ask. Modern compilers of any sophistication do not select a set of variables in the source program to store in particular registers. Instead, they try to use the available registers as effectively as possible, which may result in a single register being used to store many different variables of non-overlapping lifetimes and multiple registers being used to store a single variable at different points in time.
The variables at code generation are not the ones you know
To start, it is important to understand that variables in the source program are generally not even preserved by the time the compiler is generating code. Most compilers transform the program into some variant of single static assignment form (SSA), in which all temporary values are explicitly assigned to variables, and every variable is assigned exactly once. This answer describes SSA, but I will also provide some simple examples here. Consider the following (silly) function:
function foo(x):
let y = (x + 5) * 2
let z = x - 1
y += z * 3
return y
This function uses three variables—x, y, and z—and it reassigns y once. When translating to SSA form, the compiler will introduce an auxiliary variable for the new value instead of mutating an existing one, resulting in something like this:
function foo(x):
let y = (x + 5) * 2
let z = x - 1
let y2 = y + (z * 3)
return y2
But that’s not all: the x + 5 and z * 3 expressions are nested inside of larger expressions, and at the level of assembly language, those temporary values need to be stored somewhere. So the compiler will introduce additional auxiliary variables to store the temporaries:
function foo(x):
let t1 = x + 5
let y = t1 * 2
let z = x - 1
let t2 = z * 3
let y2 = y + t2
return y2
Now this function is in SSA form. Each statement performs exactly one computation, and its result is given a unique name. Note that the process of splitting variables like this cannot be done if variable is reassigned inside a loop, for example, but the full details of lowering to SSA are well outside the scope of this answer. For our purposes, this simple example is enough.
Allocating registers to lower from SSA to machine code
The SSA form of our foo function now uses six variables: x, t1, y, z, t2, and y2. If our target machine has at least six registers (and a sufficiently rich set of instructions for operating on them), generating machine code from the SSA is trivial. We could use a distinct register for each variable, using register A for x, B for t1, C for y, and so on, resulting in something like this (where everything after ; is a comment):
foo: ; foo(A):
add A,5,B ; B ← A + 5
mul B,2,C ; C ← B * 2
sub A,1,D ; D ← A - 1
mul D,3,E ; E ← D * 3
add C,E,F ; F ← C + E
mov F,A ; A ← F
ret ; return A
(This assumes an extremely simple architecture with at least six registers where arguments are passed and results returned in registers in order, and no registers must be preserved by the callee.)
But what if we only have three registers, A, B, and C? In that case, we have to decide how to map the six variables from our source program onto these three available registers. A natural way to think about this problem is to consider the lifetimes of each variable in foo. If we number the statements 1-6, we can draw a “timeline” that illustrates which statements each variable is “live” for, where the end of a variable’s lifetime is the statement in which it is last used:
function foo(x):
let t1 = x + 5 // (1)
let y = t1 * 2 // (2)
let z = x - 1 // (3)
let t2 = z * 3 // (4)
let y2 = y + t2 // (5)
return y2 // (6)
1 2 3 4 5 6
x ████▌
t1 ▐█▌
y ▐█████▌
z ▐█▌
t2 ▐█▌
y2 ▐█▌
This timeline diagram allows us to immediately visually understand several things about the lifetimes of the variables in our function:
We can immediately see that t1, z, t2, and y2 all last for exactly one statement, and none of their lifetimes overlap.
In contrast, x and y live across several statements, and their lifetimes overlap with those of several other variables.
This diagram allows a particularly lucid description of the problem of register allocation: we must assign a register to each row of the timeline, and if two rows in the timeline overlap, they must be assigned distinct registers. For example, we can assign the same register to both t1 and z because their lifetimes in the table do not overlap, but we cannot assign the same register to both y and z.
Given all of the above, you should hopefully be able to see how we could assign one of three distinct registers to each row of our timeline to yield a valid assignment:
1 2 3 4 5 6
A x ████▌
B t1 ▐█▌
C y ▐█████▌
B z ▐█▌
B t2 ▐█▌
B y2 ▐█▌
Mapping this back to assembly language, this yields the following code:
foo: ; foo(A):
add A,5,B ; B ← A + 5
mul B,2,C ; C ← B * 2
sub A,1,B ; B ← A - 1
mul B,3,B ; B ← B * 3
add C,B,B ; B ← C + B
mov B,A ; A ← B
ret ; return A
Note that we’ve taken a program with six variables, lowered it to machine code, and stored all of the variables in registers!
Spilling: when registers are not enough
Let’s now consider an even more impoverished machine: one with exactly one general-purpose register. This might seem unrealistically austere by modern standards, but it was quite common in the days of 8-bit microcomputers, and it will serve as a useful illustrating example. With only one register, it is simply not possible to keep all of our program’s variables in registers at all times, so some will have to be stored in memory.
On modern architectures, a natural place to store temporary variables that don’t fit in registers is the stack. Processors have instructions that allow memory to be addressed relative to the current stack pointer, or sp, which tracks the location of the top of the stack. For example, we could write something like
add A,[sp+1],A
to add the value of the A register to the value stored at an address one past the top of the stack. In C syntax, this would look something like this:
A = *(sp + 1) + A;
(Aside: Pedantic readers may complain that this architecture is highly anachronistic, featuring a single accumulator, stack-relative addressing, and an extremely rich instruction set that allows specifying the location of every operand and result. This architecture is intended as an simplifying example, and it is not intended to exactly represent the constraints of any real architecture.)
Using the stack as scratch memory essentially provides a set of “virtual registers” stored on the stack, accessed via [sp+1], [sp+2], [sp+3], and so on. (If the values to be stored are larger than a single byte, the offsets to sp would need to be larger to match, but the same principle applies.) Each of these “virtual registers” is generally referred to as a stack slot, as it is a location on the stack where a temporary may be stored.
Stack slots allow us to compile programs that need more temporaries than there are physical registers on the machine. We can try to assign as many variables to physical registers as possible and let the rest “spill over” into stack slots. For this reason, this process of placing temporaries on the stack is known as spilling.
A good register allocation algorithm will try to spill as few variables as possible. For example, we could allocate registers to our example program in the following way:
1 2 3 4 5 6
[sp+1] x ████▌
[sp+2] t1 ▐█▌
A y ▐█████▌
[sp+1] z ▐█▌
[sp+1] t2 ▐█▌
A y2 ▐█▌
But this would be a poor choice. A much better one would be to use our precious A register for short-lived temporaries and to spill the two variables that need longer lifetimes:
1 2 3 4 5 6
[sp+1] x ████▌
A t1 ▐█▌
[sp+2] y ▐█████▌
A z ▐█▌
A t2 ▐█▌
A y2 ▐█▌
The challenge of register allocation is designing an algorithm that can generate a “good” register assignment automatically.
Register allocation algorithms
Numerous register allocation algorithms exist, and I will not attempt to exhaustively describe them all in this answer. However, two algorithms are particularly well-known, and they are known as linear scan and graph coloring.
Linear scan is the simplest register allocation algorithm for practical use: it simply walks the list of variables and assigns the first register not yet assigned to an earlier variable with an overlapping lifetime. If no physical register is available, the algorithm spills to the first available stack slot.
Linear scan is easy to implement and cheap to compute, and it does surprisingly well on many real examples. Lowering to SSA does a lot of the work by splitting long lifetimes into shorter ones, and shorter lifetimes means less conflict between variables, which permits more register reuse. (It is common to say that translating to SSA reduces register pressure.)
Unfortunately, the simple, greedy nature of linear scan means there are many cases where it will not find an optimal solution, and it may spill much more than is strictly necessary. Worse, finding an optimal solution is NP-complete! This is because the problem of finding an optimal register assignment is equivalent to graph coloring, a well-known NP-complete problem.
To understand the relationship, consider the constraints that arise from the “liveness timelines” illustrated above. Each row in the timeline (and thus each variable in the program) can be thought of as the vertex in a graph, where edges connect vertices with overlapping liveness ranges. For our example program, this results in the following graph:
t1 ─ x ─ y y2
╱ ╲
z t2
Computing an optimal register assignment is now precisely the same as coloring the vertices of this graph using the fewest number of distinct colors such that no two adjacent vertices share the same color. Each color in the resulting graph corresponds to a distinct register (or, if there are not enough registers, a stack slot).
Various algorithms for graph coloring exist, but graph coloring is computationally hard, and in general, it cannot be performed in polynomial time. For this reason, even industrial-strength optimizing compilers often do not use graph coloring and thus do not find optimal solutions. For example, LLVM uses a heuristics-based greedy allocator that the LLVM developers have determined performs well enough in practice.
Scaling to real architectures
So far, this answer has discussed register allocation in the context of very simple, idealized architectures for the sake of example. Register allocation for real architectures follows the same principles, but there are numerous additional challenges to consider:
Certain instructions may only support certain registers or addressing modes for operands and results. For example, an instruction may not be able to directly use a value stored on the stack as an operand, in which case the value must be loaded into a register first. This is particularly likely to be necessary if the desired instruction is already using indirect addressing, and both register allocation and instruction selection must take those constraints into account.
Calling conventions specify how arguments are passed and returned in registers and which registers must be preserved across the call. Registers that are not callee-preserved must be spilled to the stack and loaded back into registers before and after each function call, and register allocation must take this into account.
Features of modern processors, such as out-of-order execution, CPU caches, and SIMD operations, can complicate the definition of an “optimal” register assignment. Instruction scheduling may be used to reduce inter-instruction dependencies and avoid pipeline stalls, and this often comes with register allocation tradeoffs. Register renaming performed by modern processors can help to mitigate the effects of false dependencies created by register reuse at the hardware level, but optimizing compilers generally still try to avoid generating code with such dependencies in the first place.
Code generation is a surprisingly challenging and underappreciated aspect of compiler implementation, and quite a lot can happen under the hood even after a compiler’s IR optimization pipeline has finished. Register allocation is one of those things, and like many compilers topics, entire books could be written on it alone. Still, it is my hope that this answer has provided a good place to start.
