Register Spilling

The most direct cause of spilling. A compiler's register allocator assigns program variables (virtual registers) to a finite set of physical registers. When the number of simultaneously live variables (those holding a value that may be used later) exceeds the hardware's available registers, the allocator must spill some values. This involves:

• Spill Code Generation: Inserting store instructions to save a register's value to a stack slot in memory.
• Fill Code Generation: Inserting load instructions to restore the value back into a register before its next use. The cost is the latency of these extra memory operations, which can be orders of magnitude slower than register access.

Aggressive compiler optimizations designed to improve performance can inadvertently increase register pressure, leading to spills.

• Loop Unrolling: Replicating the loop body increases the number of live variables active within a single iteration, as values from multiple logical iterations coexist.
• Function Inlining: Embedding a callee's code into the caller merges their respective live variable sets, dramatically increasing the number of values competing for registers at the inlined site. While these transformations reduce control overhead and enable other optimizations, they can push register usage beyond the architectural limit, forcing the compiler to trade one form of overhead (branch latency) for another (spill/fill latency).

Hardware and software conventions rigidly define register usage, limiting availability for general allocation.

• Caller-Saved vs. Callee-Saved Registers: Calling conventions partition registers. Caller-saved registers may be overwritten by a function call, forcing the caller to spill them before the call if their values are needed later. Callee-saved registers must be preserved by the callee, often requiring a prologue to spill them and an epilogue to restore them.
• Special-Purpose Registers: Registers dedicated to the stack pointer, frame pointer, or thread-local storage are unavailable for general allocation.
• ABI Limits: The Application Binary Interface may further restrict which registers can be used for parameter passing or return values. These fixed assignments reduce the pool of registers the allocator can use freely.

The structure of the program itself determines how long a variable must occupy a register.

• Long Live Ranges: A variable that is defined early in a function and used much later has a long live range. It ties up a register for an extended period, blocking its use for other variables and increasing the likelihood of conflict.
• Complex Control Flow: Functions with many branches, loops, and conditional paths create intricate webs of live ranges. A variable may need to be live across multiple basic blocks, making it difficult for the allocator to find a register that is free along all possible execution paths to that variable's use. This often forces a spill at the point where paths reconverge.

Register allocation is an NP-complete problem (graph coloring). Compilers use heuristic algorithms that make local decisions which can lead to suboptimal spilling.

• Spill Cost Metric: The allocator estimates the cost of spilling each variable, often based on its live range length and usage frequency within loops. A poor heuristic can spill a frequently accessed variable inside a hot loop while preserving a rarely used variable.
• Iterative Nature: After inserting spill code, the register pressure changes, potentially requiring further rounds of allocation and spilling. This can lead to spill cascades.
• Phase Ordering Problem: The order in which compiler passes run matters. An optimization (like instruction scheduling) run after allocation can increase register pressure and introduce new spills that a different ordering might have avoided.

Spilling is particularly detrimental on parallel accelerators like NPUs and GPUs due to their execution model and memory hierarchy.

• Thread Block Resource Limits: Kernel occupancy (active warps/wavefronts per core) is limited by shared memory and register usage per thread. High register use lowers occupancy, reducing latency-hiding capability. Spilling to local memory (which resides in global DRAM) is extremely slow.
• SIMT Warp Divergence: If spilling is control-flow dependent, threads within a warp may diverge, serializing memory access patterns and destroying memory coalescing.
• Memory Bandwidth Saturation: Spill/fill traffic competes with the kernel's primary data accesses for limited DRAM bandwidth, pushing performance down the memory-bound side of the Roofline Model. The goal of kernel fusion and hardware-aware optimization is often to reduce intermediate values and shorten live ranges to minimize register pressure and avoid spilling.

The compiler's register allocator is the primary defense against spilling. Modern algorithms like Graph Coloring and Linear Scan attempt to assign an unlimited number of virtual registers to a limited set of physical registers. They work by constructing an interference graph where nodes are live ranges and edges indicate conflicts. When coloring fails (i.e., more live ranges than registers), the allocator must choose which ranges to spill to memory, typically based on heuristics like spill cost (frequency of use) and distance to next use. Advanced variants like Chaitin-Briggs incorporate coalescing to reduce register pressure by merging non-interfering ranges.

Instead of spilling an entire variable's live range, the compiler can split it into shorter intervals. This technique, called live range splitting or rematerialization, breaks a long-lived variable into smaller segments, potentially allowing some segments to be assigned registers while others are spilled. A key variant is rematerialization, where the compiler recomputes a simple value (e.g., a constant or address offset) instead of reloading it from a spill slot, trading computation for memory bandwidth. This is effective for values that are cheap to recompute but have high spill costs.

The order of instructions can significantly affect register pressure. Instruction scheduling is a compiler pass that reorders operations to shorten the lifetime of variable values, reducing the number of simultaneously live variables. Techniques include:

• Local scheduling within basic blocks to move definitions closer to their uses.
• Software pipelining for loops, which overlaps iterations but can increase pressure in the kernel's prologue/epilogue.
• Scheduling loads earlier and stores later to hide memory latency introduced by spills. The goal is to create 'holes' in register usage, allowing the allocator to reuse registers more aggressively.

Loops often have high register pressure due to accumulation variables and array indices. Transformations can reduce this pressure:

• Loop unrolling increases instruction-level parallelism but also replicates variables, potentially increasing pressure. The compiler must find an optimal unroll factor.
• Loop fission (distribution) splits a loop body into multiple loops, each with lower register demand, at the cost of increased loop overhead.
• Loop tiling partitions iterations into smaller blocks, limiting the working set of array elements that must be kept in registers per tile. These transformations are often guided by profile data or auto-tuning to find the best configuration.

Developers can structure code to assist the compiler:

• Reducing variable scope: Declare variables in the innermost possible scope to minimize their live range.
• Using local variables: Encourage the compiler to keep values in registers by using stack-allocated locals instead of frequent accesses to global or heap memory.
• Explicit register hints: Some languages (e.g., C with register keyword) or compiler pragmas allow hints, though modern allocators largely ignore them.
• Algorithmic choice: Selecting algorithms with lower operational intensity or more sequential data access can reduce the number of values that must be live concurrently.
• Manual inlining/unrolling: Controlling function inlining and loop unrolling can prevent the compiler from creating code with unsustainable register pressure.

Hardware features and runtime systems can mitigate spill overhead:

• Register files: Larger physical register files directly reduce the need to spill. Architectures like GPUs have massive register files per Streaming Multiprocessor.
• Memory hierarchies: Fast, on-chip scratchpad memory (e.g., shared memory on GPUs) or L1 caches can serve as spill areas with much lower latency than main memory (DRAM).
• Compiler-managed caches: Some NPU ISAs provide instructions for explicit spill/fill to a compiler-managed cache, offering predictable latency.
• Profile-Guided Optimization (PGO): Using runtime profiles, the compiler can identify high-pressure code regions and apply more aggressive optimizations or selective spilling only on cold paths.

Register allocation is the compiler phase responsible for mapping an unlimited number of virtual program variables to a finite set of physical processor registers. Its primary goal is to keep as many live values in registers as possible. When allocation fails, it triggers register spilling. Key algorithms include:

• Graph Coloring: Models register interference as a graph, where connected variables cannot share a register.
• Linear Scan: A faster, JIT-friendly algorithm that processes variables in linear order. The allocator's decisions directly determine the frequency and cost of spills to memory.

Live variable analysis is a data-flow analysis that determines, for each point in a program, which variables hold values that may be needed in the future. A variable is 'live' from its definition to its last use. This analysis is the foundational input to register allocation and spilling decisions.

• Liveness Sets: Compilers compute sets of live variables at each instruction.
• Interference Graphs: Two variables interfere if their live ranges overlap, meaning they cannot occupy the same physical register. Accurate liveness analysis minimizes unnecessary spills by precisely identifying which values must be preserved.

Instruction scheduling is the compiler optimization that reorders machine instructions to improve instruction-level parallelism (ILP) and hide latency without changing the program's semantics. It has a complex relationship with register pressure:

• Schedule Extends Liveness: Scheduling instructions apart can lengthen the live range of a variable, increasing register pressure and potentially causing spills.
• Spill Code Introduces Latency: Inserted load/store instructions for spills create new dependencies that can stall the schedule. Advanced compilers perform integrated register allocation and scheduling to balance these competing constraints.

Loop unrolling is a transformation that replicates the body of a loop to reduce branch overhead and increase opportunities for ILP. It directly impacts register pressure:

• Increased Register Demand: Unrolling exposes more parallel operations within a single iteration, creating more simultaneously live values.
• Trade-off: While unrolling can improve performance, it can also lead to severe register spilling if the working set exceeds the register file. Compilers often use heuristics or profiling to choose an unroll factor that balances these effects.

Software pipelining is an aggressive loop optimization that overlaps instructions from different iterations to hide functional unit and memory latency. It is particularly sensitive to register pressure.

• Prologue/Epilogue: The transformed loop requires extra code to start up and drain the pipeline, increasing the number of live values across iterations.
• Modulo Scheduling: The core algorithm must find a schedule where resource usage and register demand repeat every cycle. High register demand can make a legal schedule impossible, forcing the compiler to fall back to a less aggressive optimization or increase the initiation interval, reducing performance.

Spill code refers to the load and store instructions a compiler inserts when it must spill a register's contents to memory (typically the stack). The quality of spill code generation is critical for performance.

• Spill Location Selection: Compilers choose between the stack (fast) and slower memory.
• Spill/Reload Placement: Intelligently placing spill stores after last uses and reloads just before next uses minimizes the live range of the spilled value in memory.
• Rematerialization: For some values (e.g., constants, simple computations), it's cheaper to recompute the value than to load it from memory, avoiding a spill entirely.