CPU Register Allocation
Algorithm Simulator

Enter IR code → parse live ranges → compare Graph Coloring vs Linear Scan → visualize register assignments, interference graph, and complexity.

Graph Coloring (Chaitin)

Linear Scan (Poletto-Sarkar)

8 Physical Registers

Live Range Analysis

IR Code Input

Load example:

program.ir

Registers:

Interference Graph

Algorithm Results

Allocation

Live Ranges

Analysis

Linear Scan

—

atomic operations

Spills: —

Graph Coloring

—

atomic operations

Spills: —

⬡ Linear Scan

◈ Graph Coloring

Linear Scan — Live Ranges

Graph Coloring — Register Assignment

Run the allocator on some IR code to see the analysis.

Complexity Analysis

empirical measurements across synthetic programs of varying size

Atomic Operations vs. Variables

LS grows O(n log n) · GC grows O(n²) due to edge enumeration

Wall-Clock Runtime (µs)

GC quadratic growth becomes dominant for large n

Spill Count vs. Variables

GC spills fewer variables — produces higher-quality allocation

Operations per Named Test Case

GC overhead grows faster with register pressure

Test Case Benchmark Summary

All benchmarks with 8 physical registers

Test Case	Vars	Instrs	LS Ops	LS Spills	GC Ops	GC Spills	Winner

CPU Register AllocationAlgorithm Simulator