target

Register Allocator

Many live values, few registers. Reduce the register count until the allocator has to spill, and see which value it chooses and why — under two different algorithms.

simplifiedReal allocation, simplified live ranges

Both allocators are implemented in src/compilers/sim/regalloc.ts and run on the optimized SSA of the program you type. They work on live ranges without holes: a value dead in the middle of its range still occupies a register here, where a production allocator would model the hole and reuse it. That makes linear scan slightly more pessimistic than it really is. Register names are x86-64 System V.

AtlasLang source

Examples

Function shown in the IR panels

✓ No diagnostics. The program lexes, parses and type-checks.

Available registers: 4

rax, rcx, rdx, rsi

This program needs 10 at its busiest point. Below that, some value must live in memory — no allocator can do better.

Graph colouring

Chaitin-Briggs. Better allocations, more compile time — what an ahead-of-time compiler uses.

Chaitin-Briggs graph colouring · 17 live ranges

%0rsi

%2⤓ spilled

%4rax

%6⤓ spilled

%8⤓ spilled

%10⤓ spilled

%12⤓ spilled

%14⤓ spilled

%16rdx

%19rcx

%21rax

%23rcx

%25rax

%27rcx

%29rax

%31rcx

%33rax

Why these spilled

%2 is live across 9 instructions with only 1 use, so it costs the least to keep in memory.
%6 is live across 8 instructions with only 1 use, so it costs the least to keep in memory.
%8 is live across 8 instructions with only 1 use, so it costs the least to keep in memory.
%10 is live across 8 instructions with only 1 use, so it costs the least to keep in memory.
%12 is live across 8 instructions with only 1 use, so it costs the least to keep in memory.
%14 is live across 8 instructions with only 1 use, so it costs the least to keep in memory.

Linear scan

Sort by start point and sweep. Much faster, worse code — what a JIT uses, because the compile happens while the user waits.

Linear scan · 17 live ranges

%0⤓ spilled

%2rcx

%4rdx

%6rsi

%8⤓ spilled

%10⤓ spilled

%12⤓ spilled

%14⤓ spilled

%16⤓ spilled

%19rax

%21rdx

%23rcx

%25rax

%27rsi

%29rdx

%31rcx

%33rax

Why these spilled

%0 stays live until instruction 16, longer than %8, so it blocks a register for longer. Linear scan spills the later-ending interval.
%8 stays live until instruction 11, longer than %19, so it blocks a register for longer. Linear scan spills the later-ending interval.
No register was free at instruction 5, and every active value ends later than %10 does.
No register was free at instruction 6, and every active value ends later than %12 does.
No register was free at instruction 7, and every active value ends later than %14 does.
No register was free at instruction 8, and every active value ends later than %16 does.

What came out

A spilled value becomes a stack slot, and the extra memory traffic is visible in the listing.

31 instructions · frame 48 bytes

.globl spread
spread:
  push rbp   ; establish the frame pointer
  mov rbp, rsp
  sub rsp, 48   ; 6 spilled values, 8 bytes each
.Lspread_b0:   ; entry
  mov rsi, rdi   ; parameter 0: n
  lea [rbp-8], [rsi+1]   ; add with a distinct destination selected as lea
  lea rax, [rsi+2]   ; add with a distinct destination selected as lea
  lea [rbp-16], [rsi+3]   ; add with a distinct destination selected as lea
  lea [rbp-24], [rsi+4]   ; add with a distinct destination selected as lea
  lea [rbp-32], [rsi+5]   ; add with a distinct destination selected as lea
  lea [rbp-40], [rsi+6]   ; add with a distinct destination selected as lea
  lea [rbp-48], [rsi+7]   ; add with a distinct destination selected as lea
  lea rdx, [rsi+8]   ; add with a distinct destination selected as lea
  mov rcx, [rbp-8]
  add rcx, rax
  mov rax, rcx
  add rax, [rbp-16]
  mov rcx, rax
  add rcx, [rbp-24]
  mov rax, rcx
  add rax, [rbp-32]
  mov rcx, rax
  add rcx, [rbp-40]
  mov rax, rcx
  add rax, [rbp-48]
  mov rcx, rax
  add rcx, rdx
  mov rax, rcx
  add rax, rsi
  mov rsp, rbp
  pop rbp
  ret