In my last post, I explained a bit about how to retrofit SSA onto the original linear scan algorithm. I went over all of the details for how to go from low-level IR to register assignments—liveness analysis, scheduling, building intervals, and the actual linear scan algorithm.
Basically, we made it to 1997 linear scan, with small adaptations for allocating directly on SSA.
This time, we’re going to retrofit lifetime holes.
Lifetime holes
Lifetime holes come into play because a linearized sequence of instructions is not a great proxy for storing or using metadata about a program originally stored as a graph.
According to Linear Scan Register Allocation on SSA Form (PDF, 2010):
The lifetime interval of a virtual register must cover all parts where this register is needed, with lifetime holes in between. Lifetime holes occur because the control flow graph is reduced to a list of blocks before register allocation. If a register flows into an else -block, but not into the corresponding if -block, the lifetime interval has a hole for the if -block.
Lifetime holes come from Quality and Speed in Linear-scan Register Allocation (PDF, 1998) by Traub, Holloway, and Smith. Figure 1, though not in SSA form, is a nice diagram for understanding how lifetime holes may occur. Unfortunately, the paper contains a rather sparse plaintext description of their algorithm that I did not understand how to apply to my concrete allocator.
Thankfully, other papers continued this line of research in (at least) 2002, 2005, and 2010. We will piece snippets from those papers together to understand what’s going on.
Let’s take a look at the sample IR snippet from Wimmer2010 to illustrate how lifetime holes form:
... continue reading