Course contentsShow
← Computer Science
Lesson 2052 of 2,87246. Compilation and InterpretationFree lesson

Register Allocation Basics

Assigning variables to limited physical registers requires graph coloring or linear scan algorithms.

Register Allocation Basics

What you'll learn: How compilers assign program variables to the CPU's limited physical registers using graph coloring or linear scan algorithms.

The Challenge

After translating your high-level code into three-address code or other IR, the compiler faces a crucial problem: your program might use dozens or hundreds of variables, but the CPU typically has only 8–32 general-purpose registers. Since register access is 10–100× faster than memory access, register allocation determines which variables live in registers at each point in your program.

The Core Problem

Imagine you have 50 variables but only 16 registers. Variables used frequently should stay in registers, while others can be "spilled" to memory. The trick is: not all variables are "live" (in use) at the same time. Two variables that never overlap in their lifetimes can share the same register.

Think of it like hotel room booking: If one guest checks out Monday and another arrives Tuesday, they can use the same room. The hotel (register) is reused when availability permits.

Two Main Approaches

Graph Coloring

Build an "interference graph" where each variable is a node, and edges connect variables that are live simultaneously (they "interfere"). Assign registers by coloring the graph so no adjacent nodes share a color. Each color represents one physical register. If you can't color with k colors (where k is your register count), some variables must spill to memory.

Linear Scan

Process variables in order of their live ranges (intervals where they're used). Assign free registers greedily. When registers run out, spill the variable whose next use is farthest away. Faster but less optimal than graph coloring.

Key Takeaway: Register allocation uses graph coloring or linear scan algorithms to map many program variables onto a few physical registers, maximizing performance by keeping frequently-used data in fast storage while spilling less-critical variables to memory.