Linear Scan with Lifetime Holes
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 seq