Register allocation

Advanced

Introduction

Intermediate code uses as many temporaries as it likes. A real processor has only a few registers (x86-64 has 16 general-purpose ones), and reaching memory is many times slower than reaching a register. Register allocation decides which values get registers, and when two values can share one. It is one of the optimizations with the biggest effect on speed, and it uses the liveness analysis from the control-flow lesson.

How it works

Number the instructions 1, 2, 3, … A value's live range runs from the instruction that writes it to the last instruction that reads it. Inputs that are read but never written are live from the start (line 0). Written as (start, end], a range does not include its start: an instruction reads its operands before writing its result, so a value read for the last time on line 3 and a value written on line 3 can use the same register.

Two values interfere if their ranges overlap; then they need different registers. The register pressure after a line is the number of ranges that cover it, and the largest pressure is the fewest registers that avoid spilling for straight-line code.

Graph colouring. Make a graph with a node per value and an edge between every pair that interferes. Giving each node one of k colours so that no edge joins two nodes of the same colour is exactly a register assignment with k registers. Finding the fewest colours is hard in general, so compilers use heuristics such as Chaitin's: repeatedly remove a node with fewer than k neighbours (it can always be coloured later); if none exists, choose one to spill.

Linear scan is simpler and faster. Visit the ranges in order of their start:

  1. first, expire every active range that has ended (end ≤ this start), freeing its register;
  2. if a register is free, take the lowest-numbered one;
  3. otherwise spill: of the active ranges and the new one, the range that ends furthest away goes to memory. If that is an active range, the new range takes its register.

A spilled value lives in memory: the compiler adds a store after it is written and a load before each use. Spilling the range that ends last frees a register for the longest time.

Syntax

for name in sorted_by_start:
    expire ranges with end <= start[name]
    if free: give name the lowest free register
    else:
        victim = active range with the largest end
        if end[victim] > end[name]: name takes victim's register; spill victim
        else: spill name

Example

program = """a = x + y
b = a * 2
c = x - 1
d = b + c
e = d * a
f = e - y
print f""".splitlines()

start, end = {}, {}
for number, line in enumerate(program, start=1):
    words = line.split()
    dest, read = (None, words[1:]) if words[0] == "print" else (words[0], words[2:])
    for word in read:
        if word.isidentifier():
            start.setdefault(word, 0)
            end[word] = number
    if dest:
        start[dest] = number
        end.setdefault(dest, number)
names = sorted(start, key=lambda n: (start[n], n))
print("live ranges:", ", ".join(f"{n} ({start[n]},{end[n]}]" for n in names))

pressure = [sorted(n for n in names if start[n] <= gap < end[n]) for gap in range(len(program))]
busiest = max(range(len(program)), key=lambda gap: len(pressure[gap]))
print(f"most values live at once: {len(pressure[busiest])}, after line {busiest} ({' '.join(pressure[busiest])})")


def linear_scan(k):
    free, active, register, log = set(range(1, k + 1)), [], {}, []
    for name in names:
        for other in [o for o in active if end[o] <= start[name]]:
            active.remove(other)
            free.add(register[other])
        if free:
            register[name] = min(free)
            free.remove(register[name])
            active.append(name)
            log.append(f"{name} -> r{register[name]}")
            continue
        victim = max(active, key=lambda o: (end[o], o))
        if end[victim] > end[name]:
            register[name] = register.pop(victim)
            active.remove(victim)
            active.append(name)
            log.append(f"{name} -> r{register[name]} ({victim} is spilled to memory)")
        else:
            log.append(f"{name} -> memory")
    return log


for k in (3, 4):
    print(f"with {k} registers:")
    for line in linear_scan(k):
        print("   ", line)
Open in compiler

Line by line

  1. The first loop finds each value's live range; x and y are inputs, so they start at 0.
  2. After line 2, four values are live (a, b, x and y), so four registers avoid spilling.
  3. With three registers, b arrives when x, y and a hold all three. y's range ends last (line 6), later than b's, so y is spilled and b takes its register.
  4. Registers are reused as ranges end: c takes x's register, and d, e and f each take a register freed on their own line.
  5. With four registers nothing is spilled.

Expected result

live ranges: x (0,3], y (0,6], a (1,5], b (2,4], c (3,4], d (4,5], e (5,6], f (6,7]
most values live at once: 4, after line 2 (a b x y)
with 3 registers:
    x -> r1
    y -> r2
    a -> r3
    b -> r2 (y is spilled to memory)
    c -> r1
    d -> r1
    e -> r1
    f -> r1
with 4 registers:
    x -> r1
    y -> r2
    a -> r3
    b -> r4
    c -> r1
    d -> r1
    e -> r1
    f -> r1

In the real world

Linear scan was designed for just-in-time compilers, where compiling must be fast; the HotSpot JVM's client compiler and several JavaScript engines use variants of it. GCC's allocator is based on graph colouring, and LLVM uses its own "greedy" allocator that splits live ranges to avoid spills. Compiler Explorer (godbolt.org) shows how the same function compiles to different register choices at different optimization levels.

Common mistakes

  • Including a range's start in the overlap test, which wastes registers on values that never coexist.
  • Forgetting the inputs, which are live from the very start.
  • Spilling the newest value by habit instead of the one that ends furthest away.
  • Not freeing registers when ranges end, so allocation runs out much too early.

Best practices

  • Compute liveness carefully first; allocation is only as good as the live ranges.
  • Measure the register pressure before allocating, to see whether spilling is unavoidable.
  • Prefer to spill values used rarely, such as those outside loops; real allocators weigh spill costs by how often each use runs.

Summary

Each value has a live range from its definition to its last use. Values whose ranges overlap interfere and need different registers; the maximum overlap is the number of registers needed without spilling. Graph colouring and linear scan both turn that into an assignment, spilling to memory when registers run out.

Quick check

1. When can two values share a register?
2. x is read for the last time on line 3, and c is written on line 3. Can they share a register?
3. In linear scan with no free register, which value is spilled?
4. What does a register-allocation colour stand for?

Key takeaways

  • Two values can share a register if their live ranges do not overlap.
  • If more values are live at once than there are registers, something must be spilled.
  • Linear scan spills the value whose range ends furthest away, because it would block a register the longest.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.