Register Allocation and the Occupancy Ceiling

Register allocation on a GPU is the same graph-colouring problem as on a CPU, with one difference that changes the entire trade: the allocation is not a per-thread decision but a per-warp reservation made for the warp’s whole lifetime. A thread’s registers are never returned while it runs, so the number the compiler picks determines how many warps can be resident, and residency determines how much latency the SM can hide. A change of one register per thread can be worth more than a rewrite of the inner loop.

The mechanism is worth following from the colouring problem down to the launch, because the coupling between the two is where the surprises are.

From liveness to a per-warp reservation

The compiler builds an interference graph over the values in a kernel: two values interfere if one is live at a definition of the other. Colouring that graph with k colours gives a register assignment using at most k registers per thread. When the graph cannot be coloured with k colours, some values are spilled, written to local memory, which is backed by the same memory hierarchy as global memory and carries a similar latency. Spilling is not a correctness failure; it is a large, sometimes catastrophic, performance decision made by the compiler under a constraint it was given.

The constraint is the register budget. The compiler picks a target count from a heuristic, which on GPU compilers typically starts at the architecture’s maximum per-thread registers (255 is the usual architectural cap) and is reduced only if the kernel’s launch bounds declare a minimum occupancy. Left alone, the compiler will happily use a large register count for a kernel with heavy unrolling, because doing so avoids spills and shortens the instruction stream.

That is a perfectly good objective for a CPU. On a GPU it competes directly with latency hiding, because the register file is finite and the warps that fit are floor(registers_per_SM / (registers_per_warp)). The per-warp figure is not 32 × registers_per_thread exactly: the hardware allocates in fixed-size units, so a warp using 33 registers per thread may be charged for 40, and the charge is rounded up to the granularity of the file’s banking. The rounding is the reason that register counts near a boundary behave discontinuously.

registers_per_SM = 65536            /* illustrative, architecture-specific */
alloc_unit       = 8                /* per-thread registers, rounded up   */
max_warps        = 64

regs/thread  allocated/warp  warps   occupancy
     32          1024          64      100%
     33          1280          51       80%   (rounded to 40 regs/thread)
     40          1280          51       80%
     48          1536          42       66%
     64          2048          32       50%
     96          3072          21       33%

The step from 32 to 33 registers per thread costs thirteen warp slots. Nothing about the code changed except one live value. This is the discontinuity that makes register count a first-class performance variable rather than a compiler detail.

Why the file cannot be shared

The reason a warp’s reservation is fixed for its lifetime is the addressing scheme. A register operand in an instruction names a register number, not a physical location, and the mapping from register number to a physical slot is a property of the warp, established at launch. With up to 255 registers named per thread and thirty-two lanes, the file is banked so that a full warp’s operand fetch can be served in one cycle, and the banks are addressed by the warp’s assigned base. Reassigning slots mid-flight would require rewriting every outstanding instruction’s operand mapping, which the pipeline cannot do.

This is the same reason a warp cannot be partially evicted: the register file holds thirty-two lanes’ worth of state for each named register, and there is no mechanism to spill a subset of lanes. A warp with eight active lanes occupies the same slots as a warp with thirty-two, which is why the occupancy figure in what occupancy actually counts treats all warps as equal consumers regardless of their masks.

The file’s capacity is also why the architectural maximum per-thread register count is what it is. With 65536 registers per SM and 2048 threads, the average available per thread is 32. The 255-register maximum is only reachable at very low occupancy: a kernel at 255 registers per thread supports eight warps per SM, one-eighth of the maximum. That configuration exists for kernels that need a large working set per thread, typically long unrolled sequences of dependent arithmetic, and it is a deliberate trade rather than an accident.

What forcing the count down buys and costs

The programmer’s lever is a launch bound declaring a minimum number of blocks per SM and a maximum number of threads per block, or an explicit maximum register count per thread. Declaring the bound makes the compiler colour the graph with a smaller palette, spilling what does not fit.

Spilling has a specific signature. A spilled value is stored to a per-thread region of local memory and reloaded when needed; the store and the load are real memory operations with the latency of the memory hierarchy, and they are per-lane so they coalesce like any other access. The cost is therefore two memory operations per spill-reload pair, added to a kernel whose occupancy was raised to hide memory latency in the first place. The exchange is not obviously favourable, and it fails outright when the spill traffic exceeds what the extra warps can hide.

The trade has a rough shape. Going from 64 registers to 32 doubles the resident warps but may add a handful of spill-reload pairs per loop iteration. If the loop body has ten arithmetic instructions and no memory access, the added traffic turns a compute-bound kernel into a memory-bound one and the occupancy gain cannot compensate. If the loop body already has a long-latency load, the extra warps are pure gain and the spills ride along in the shadow of the existing stall. The direction of the trade is set by whether the kernel was latency-limited or throughput-limited before the change.

Unrolling is where the register count comes from

Most high register counts are produced by loop unrolling. Unrolling n iterations removes n-1 branch instructions and n-1 loop-counter updates, and lets the scheduler interleave the unrolled iterations’ independent operations. It also multiplies the number of simultaneously live values, and each of those needs a register. The compiler unrolls until the register budget binds.

This means the register count and the instruction count are coupled through a knob the programmer rarely touches directly. A #pragma unroll with an explicit factor, or its absence, changes both. The useful discipline is to check the reported register count after each change to the loop structure, because the compiler’s heuristic responds to instruction-level structure in ways that are not visible in the source’s shape. A function inlined into a loop body, a common subexpression hoisted out, or a temporary kept live across a barrier can each move the count across a boundary.

Occupancy also constrains unrolling indirectly through the barrier structure. A block that must synchronize has to have enough warps to fill the block’s work between barriers, and enough blocks resident to fill the SM. Unrolling that raises the register count may reduce resident blocks below the number needed to cover a barrier’s drain, which is a loss that does not appear in the occupancy percentage because the percentage is computed per SM rather than per block.

The measured count and the compiled count

The register count reported by the compiler’s resource usage output is the static allocation, and it is the number the occupancy formula uses. It is not necessarily the number of registers the kernel would benefit from. Two effects blur the relationship.

The first is that a kernel’s register demand is not uniform across its execution. The peak liveness occurs in one region, often a deeply nested loop or a long expression, and the rest of the kernel uses a fraction of the allocation. Since the allocation is per warp and static, the peak sets the cost for the whole kernel. Splitting the peak region into a separate kernel, or restructuring so the peak does not overlap with the rest, can lower the count without any loss.

The second is that the compiler’s allocator is not optimal, and its choices near the boundary are coarse. A kernel at 34 registers that could fit 32 with better scheduling is charged for 40 and loses the warp slots. Reordering operations to shorten live ranges, or reducing the number of live accumulators, is sometimes enough to move it back below the boundary, and the gain is a step function rather than a gradual improvement.

Both effects argue for treating the register count as a design parameter with a target, chosen by working backward from the latency the kernel must hide. A kernel that needs 32 warps to cover its memory latency has a budget of 64 registers per thread on an SM that holds 64 warps, because half the file is then enough; a kernel that needs every warp slot the SM has gets 32 registers per thread instead. Setting the budget first and letting the compiler fit it is the reverse of the default order, and it produces a more predictable result because the occupancy outcome is decided before the code shape is.

Where the budget cannot be met without spills, the remaining option is to change what the kernel keeps live: recompute a value instead of holding it, or move a per-thread accumulator into shared memory. The first trades arithmetic for registers, the second trades registers for a different resource with its own limits, and both are preferable to spilling to local memory when the spill is on the critical path. Which of these is available depends on the kernel’s structure, and the choice is the same one that governs latency hiding arithmetic: the goal is never the highest occupancy, only enough warps to cover the stall, with the rest of the register file spent on shortening the instruction stream.