Linear Scan with Lifetime Holes
16 days ago
- #linear-scan
- #compiler-optimization
- #register-allocation
- Explains the concept of retrofitting lifetime holes into linear scan register allocation.
- Discusses how lifetime holes occur due to the control flow graph being reduced to a list of blocks.
- References key papers on linear scan register allocation (1998, 2002, 2005, 2010) for understanding lifetime holes.
- Provides a sample IR snippet to illustrate how lifetime holes form in register intervals.
- Describes modifications needed to the interval data structure to support multiple ranges (lifetime holes).
- Details the implementation changes required for the register allocator to handle lifetime holes.
- Compares the original Poletto1999 algorithm with the modified Mössenböck2002 algorithm to highlight changes for lifetime holes.
- Explains the role of the inactive set in managing intervals with lifetime holes.
- Notes that resolution and SSA deconstruction can remain unchanged despite the addition of lifetime holes.
- Concludes with the benefits of adding lifetime holes, such as better allocation for short-lived virtual registers.