# Coalescing by register allocation

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?

## 1 Answer

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.

• Great answer, but I have two questions regarding it. First, you mentioned that "spill code" is basically splitting the variable in to parts and saving parts in registers and others in main memory. How can a variable be even split? I thought "spill code" is just to save the variable in main memory. Last but not least, why do I need t1 in your example? Why can't p() be stored directly to r1? Commented Mar 11, 2018 at 7:09
• On the second question, I thought I answered that, but I may not have been clear. What would you do if q() involves a function call? Then r1 is probably part of the calling convention of that function, and so you can't store the result of p() in that register. Introducing a temporary lets the register allocator handle this in a uniform way, assigning the result of p() to r1 if it's safe and efficient to do so. Commented Mar 11, 2018 at 7:13
• On the first question: you're not really splitting the variable, you're splitting its lifetime. You can think of a register spill as temporarily storing a value that should be in a register into memory, but you can also think of the spill location as a different variable with a different lifetime. If you look at the live range splitting example, x1 is not actually live during the inner loop. Did that help? Commented Mar 11, 2018 at 7:19
• Great explanation! It answered my questions about coalescing in terms of register allocation and spill code! Commented Mar 11, 2018 at 7:30