Linear Scan with Lifetime Holes

Summary

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: 16: label B1(R10, R11): 18: jmp B2($1, R11) # vvvvvvvvvv # 20: label B2(R12, R13) 22: cmp R13, $1 24: branch lessThan B4() else B3() 26: label B3() 28: mul R12, R13 -> R14 30: sub R13, $1 -> R15 32: jump B2(R14, R15) 34: label B4() # ^^^^^^^^^^ # 36: add R10, R12 -> R16 38: ret R16 Virtual regi...