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.