---
title: Register Allocation
url: https://doc.liz6.com/en/compilers/05-optimization/03-register-allocation
locale: en
area: compilers
tags:
- compilers
- optimization
date: 2026-06-30
modified: 2026-07-16
description: 'The stage in compiler optimization that best demonstrates NP-hardness: mapping infinite virtual registers to a finite number of physical registers, and spilling to the stack when they do not fit. Graph coloring (Chaitin/Briggs) and linear scanning (Poletto/Sarkar) are two approximate solutions; the chordal graph property of SSA makes coloring easier.'
---

# Register Allocation

> The stage in compiler optimization that best demonstrates NP-hardness: mapping infinite virtual registers to a finite number of physical registers, and spilling to the stack when they do not fit. Graph coloring (Chaitin/Briggs) and linear scanning (Poletto/Sarkar) are two approximate solutions; the chordal graph property of SSA makes coloring easier.

## Overview

The [SSA form](/compilers/04-intermediate-representation/01-ssa-form.md) and [optimization](/compilers/05-optimization/01-data-flow-analysis.md) phases use **infinite virtual registers**—each new value gets its own `%v1`, `%v2`. The actual target machine has only a small number of physical registers (x86-64 has 16 general-purpose registers, ARM64 has 31) and is constrained by the calling convention. Register allocation is the process of mapping virtual registers to physical registers—when they don't fit, they **spill** to the stack. This is the part of compiler optimization that most clearly demonstrates NP-hardness—optimal register allocation is NP-complete (equivalent to graph coloring), so approximate algorithms are used in practice.

## Prerequisite: Liveness Analysis

Liveness from [data flow analysis](/compilers/05-optimization/01-data-flow-analysis.md) directly provides input for register allocation:

```
For two virtual registers v1 and v2:
  If there exists a program point where v1 and v2 are both live
    → v1 and v2 cannot share the same physical register
    → There is an edge between v1 and v2 in the interference graph
```

Construction of live ranges: Starting from each definition point, follow the SSA def-use chain to all use points; the "segments" between them constitute the live range of that virtual register. If there are phi merges, connect the live ranges of the phi sources and targets.

## Graph Coloring Allocation (Chaitin/Briggs)

### Constructing the Interference Graph

Nodes = virtual registers; Edges = two virtual registers are simultaneously live at any point:

```
v1 is defined in BB1, last used in BB3
v2 is defined in BB2, last used in BB3
At the entry of BB3, both v1 and v2 are live → there is an edge v1 — v2
```

### Coloring = Assigning a color (physical register) to each node, such that adjacent nodes have different colors

Algorithm (Chaitin-style):

```
while there are still nodes in the graph:
    if there exists a node n with degree(n) < K (K = number of available physical registers):
        Remove n from the graph and push n onto the stack       ← n can definitely be colored (adjacent nodes < K)
    else:
        Select node s with the lowest spill cost
        Mark s as spilled, remove it from the graph             ← Sacrifice it, place it on the stack
        Call spill_code(s): Generate store/load instructions to move s's value to the stack

Pop nodes from the stack one by one, assigning a color to each (ensuring no conflict with already-colored adjacent nodes)
```

**Briggs' Improvement**: Do not immediately conclude that nodes with `degree < K` are colorable—optimistically remove them first. If, during the pop phase, a node cannot be colored, then perform a spill. Briggs' optimistic coloring produces significantly fewer spills in practice than Chaitin's pessimistic algorithm (Chaitin actively spills all nodes with degree ≥ K, many of which could have been colored).

### Spill Code Generation

When registers are insufficient, "spill" the value of a virtual register to the stack:

```
Before spill:                     After spill:
  v1 = ...                         v1 = ...
  ... = v1 (use)                   spill [v1_slot] = v1        ← Store immediately after definition
                                    v1_reload = load [v1_slot]  ← Load before use
                                    ... = v1_reload
```

However, spilling changes the live range—originally, v1 was only used at `... = v1`, but spilling splits its live range into two segments (`v1` and `v1_reload`), potentially making the interference graph sparser and thus alleviating coloring pressure. **Rebuild the interference graph and re-allocate after spilling**—this is an iterative process.

## Linear Scanning (Poletto/Sarkar): Faster but More Spills

Linear scanning uses a simplified liveness model: instead of point-precise interference graphs, it relies on the **linear order of live intervals**:

```
Sort all virtual register live intervals by start position:
  Maintain a "currently active" list
  Scan each interval:
    expire_old_intervals()  ← Remove ended intervals, freeing their physical registers
    if there is a free register:
        Allocate it
    else:
        Select the currently active interval with the lowest spill cost, spill it
        Allocate the freed register to the new interval
```

The complexity of linear scanning is O(n log n) (due to sorting), which is much faster than graph coloring's O(n²) or higher. The cost: it produces more spills than graph coloring (because it doesn't look at the interference graph, it might spill two non-interfering intervals). Linear scanning is commonly used in JIT compilation—compilation time is paramount, and a few extra spills are acceptable.

## Benefits of SSA for Register Allocation

In SSA form, the def-use relationships between variables naturally form a **chordal graph** structure—coloring chordal graphs can be solved optimally using a greedy algorithm in O(n). However, note that actual register allocation usually occurs after SSA destruction (inserting copies); the copies introduced by phi destruction may break the chordal graph property. Nevertheless, the coalescing phase will try to merge these copies as much as possible, keeping coloring efficient.

## Coalescing: Eliminating Copies

```
v1 = ...
v2 = v1           ← Copy: requires a mov instruction
... = v2

If v1 and v2 are assigned the same register r:
  r = ...
  ... = r         ← Copy is eliminated
```

Coalescing is not without cost—merging v1 and v2 into a single node may increase its degree, making it uncolorable. Therefore, coalescing is **conservative**: it only coalesces copies that will not introduce spills after coloring. Briggs' conservative coalescing checks if the merged node's degree < K (available registers); George's conservative coalescing checks if all adjacent nodes of v1 are "already non-conflicting with v2 or have degree < K".

## Calling Convention and Allocator Interactions

Physical registers are constrained not only by virtual register contention but also by the calling convention:

- **Argument registers** (x86-64: `rdi, rsi, rdx, rcx, r8, r9`): The first 6 arguments of a function call must be placed in these registers.
- **Return value register** (`rax`): The function return value is in rax.
- **Callee-saved** (x86-64: rbx, rbp, r12–r15): If the called function modifies these registers, it must restore them before returning. The called function handles spill/restore; the caller does nothing.
- **Caller-saved** (x86-64: rax, rcx, rdx, rsi, rdi, r8–r11): If the caller needs to use these registers before and after a call, it must handle spill/restore itself.

The register allocator must adhere to these constraints: **spill callee-saved physical registers to the stack in the function prologue** if they are used during allocation; before and after call instructions, do not assume that values in caller-saved physical registers will survive the call.

## References

- **Chaitin (1982)**: "Register Allocation and Spilling via Graph Coloring" — The original paper on graph coloring allocation
- **Poletto/Sarkar (1999)**: "Linear Scan Register Allocation" — The original paper on linear scanning
- **LLVM**: `lib/CodeGen/RegAllocGreedy.cpp` (default allocator), `lib/CodeGen/RegAllocBasic.cpp` (baseline) — Industrial-grade allocators, combining linear scanning and graph coloring

*Keywords: register allocation, interference graph, graph coloring, Chaitin, Briggs, optimistic coloring, linear scan, spilling, spill code, splitting, coalescing, copy elimination, liveness, live range, chordal graph, register pressure, caller-saved, callee-saved, calling convention, prologue, epilogue, SSA-based allocation*