Register Allocation

The purpose of register allocation is to determine which variable should be stored in which register. See Expression (Assembly), where we need to evaluate these variables.

• Register allocation = the process of assigning registers to variables.
• Memory allocation = the process of assigning memory addresses to variables.

The simplest solution is to greedily assign the available registers to each variable. However, it turns out that multiple variables can share the same register.

Consider the value a+b+c+d+e, which can be shared in a single register.

To determine whether a variable can be shared, we define the notion of liveness: a variable v is live at program point p if the value stored in v at p may be read from v sometime after executing p.

In a sequence of instructions, a program point is the location in between any two consecutive instructions. In the example below, at the point just after the first line, variable t1 is live because its value will be read in the third line.

t1 := a*b
t2 := c*d
t3 := t1 + t2

Given a variable v, the live range of v is the set of all program points p at which v is live. Then two variables can share the same registers if their live ranges are disjoint, A variable can be dead for one of two reasons:

1. There are no reads of the variable after the current program point.
2. It will be overwritten before it is read.

Exercise: Write the set of variables that are live at each point. Include only the temporary variables whose names start with t.

t1 := a * b
	// live set : { t1 }
t2 := c * d
	// live set : { t1, t2 }
t3 := t1 + t2
	// live set : { t3 }
t4 := e * f
	// live set : { t3, t4 }
t5 := t3 - t4
	// live set : { t5, t3 }
g := t3 + t5
	// live set : { }

Using these life sets, we can summarize the information in an Interference Graph.

A valid register allocation corresponds to a colouring of the interference graph. A graph colouring is an assignment of colours to the vertices of a graph such that every edge connects two vertices with different colours.

For the example above, we have the following Interference Graph, so a valid graph colouring would be assigning t1, t3 to Reg(1), and assigning t2, t4, t5 to Reg(2).

ECE222

Most programs have more variables than registers. Therefore, we keep the most frequently used variables in registers, and the rest are placed in memory. We use loads and stores to move variables between registers and memory.

The process of putting less frequently used variables into memory is called spilling registers.

Related

• Interference Graph