Coalescing by register allocation

Question

I have a rough idea of what coalescing in terms of memory access by threads is, but now, when learning about compilers, the term coalescing also appears when talking about register allocation.

In my book, it is just briefly mentioned, that coalescing for register allocation is just merging nodes from the graph (I assume the nodes of the graph show the variables that can be stored in a register).

Can someone explain a bit more thoroughly what coalescing in this sphere means?

Answer 1

In this context, "coalescing" means eliminating variable-to-variable move operations in the register allocator by allocating those two variables to the same location, typically the same register.

It may not be obvious why you'd do this in the register allocator, as opposed to in an earlier optimisation like constant folding. The reason is that code generation might introduce loads and stores for convenience or optimisation purposes.

The way that register allocation is often presented, you generate an assignment of "variables" to "locations", where a location could be a register or spilled. That's a good mathematical model of the problem, but it's a bit more complicated than this in practice.

Look at live range splitting as one example. This is an optimisation where a variable is not held in the same place for its lifetime ("spilling" can be thought of as a special case). As a concrete example, consider the case of two nested loops with a variable that is used a lot in the inner loop:

x <- something();
for (outer loop) {
    some_computation();
    for (inner loop) {
        some_other_computation_involving(x);
    }
}
use(x);

It seems like we probably want to store x in a register in the inner loop, but we may not want to store it in a register in the outer loop, because that would tie up a register during some_computation. On the other hand, there may be enough registers to keep x in a register, depending on how allocation for some_computation works out.

One solution is to split the range of variable x into two:

x1 <- something();
for (outer loop) {
    some_computation();
    x2 <- x1;
    for (inner loop) {
        some_other_computation_involving(x2);
    }
    x1 <- x2;
}
use(x1);

That introduces two variable-to-variable moves. If we allocate x1 and x2 to different locations, we are essentially spilling x for some of its lifetime. But using a coalescing-aware allocator, we have the chance that the spill may never happen if the moves are coalesced.

Another interesting case is that of special-purpose registers and calling conventions. Suppose, for example, you are calling a function:

x <- f(p(), q());

We will also suppose that the calling convention for this architecture requires the first argument for the call to f to be in register r1 and the second argument to be in register r2. One way to do this is to generate code like this:

t1 <- p()
r2 <- q()
r1 <- t1
call f

Again we have introduced a variable-to-variable move. A coalescing-aware register allocator can then decide whether to "spill" t1 or to generate it directly in r1:

r1 <- p()
r2 <- q()
call f

I use the word "spill" advisedly here because it might also be appropriate it to "spill" it to another register:

r3 <- p()
r2 <- q()
r1 <- r3
call f

Since r1 plays an important role in the calling convention, it may be needed for computing q().

Callee-save/caller-save registers can also be implemented using this mechanism.