Register Allocation

Hypothetical code sequence:

...

-- x and y are in registers (alive) before

t1 := x + 1;

t2 := y + t1;

t3 := y * t2;

z := x + t3;

-- want x and z to be in registers (alive) after

...

Register allocation can be treated as a graph-colouring problem.

Register Allocation Graph

Vertices (variables):

x, y, z, t1, t2, t3

Edges (where (v1, v2) are alive at same times):

(x,y), (x,z), (x,t1), (x,t2), (x,t3),

(y,t1), (y,t2)

 

Possible register allocation (vertex colouring):

R1: x

R2: y, z

R3: t1, t2, t3

 

Other choices are possible but we need at least 3 registers, e.g., for a typical 2-address machine:

-- x in R1 and y in R2
load R3, R1
add R3, literal 1	-- t1 := x + 1
add R3, R2	-- t2 := y + t1
mult R3, R2	-- t3 := y * t2
load R2, R1
add R2, R3	-- z := x + t3
-- x in R1 and z in R2