Register Allocation

Definition

The purpose of register allocation is to allow us to determine which variable should be stored in which register, since there are a limited number of registers.

Live Variable

Definition

A variable is live at a program point if its current value is read in the future

Example

E.g the expression a + b + c + d + e:

// Nothing live
t1 = a + b
// t1 live
t2 = t1 + c
// t2 live, t1 dies
t3 = t2 + d
// t3 live, t2 dies
t4 = t3 + e
// t4 live, t3 dies

Live Range

Definition

The live range of a variable is set of program points where it is live

Info

Variables can share a register if their live ranges don't overlap. The compiler can scan the program to determine live ranges.

Interference Graph

Definition

An interference graph has a vertex for each variable, and edges between variables, whose live ranges interfere (i.e overlap)

Graph colouring: assigns "colours" to vertices such that any adjacent vertices have distinct colours. Each colour represents a different register. Our goal is to create the best graph colouring possible.

Deciding on a minimal graph colouring is an NP-complete problem.

Example

// None live
t1 = a * b
// t1 live
t2 = c * d
// t1, t2 live
t3 = t1 + t2
// t3 live
t4 = e * f
// t3, t4 live
t5 = t3 - t4
// t3, t5 live
g = t3 + t5
// None live

Best colouring:

t1 and t3 in register 1
t2, t4 and t5 in register 2

r1 = a * b
r2 = c * d
r1 = r1 + r2
r2 + e * f
r2 = r1 - r2
g = r1 + r2