Register Allocation via Graph Coloration – Part II

Overview of Register Allocation by Graph Coloration
A programmer makes use of variables ( eg a, b, c, x1, y ) in writing high-level program codes. At some point in time the compiler would have to replace this variables using registers. This happens in the code-generation phase of the compilation process.

While the programmer does not have a limit to the number of variables he can use, hardware on the other hand have a limited amount of memory. So the challenge is how a limited number of registers in the CPU can be allocated to indefinite number of variables used by the programmer?

Register allocation is the process of determining which values should be placed into which registers and at what times during the execution of the program.

Register Allocation by Graph Coloration
When formulated as a coloring problem, each node in the graph represents the live range of a particular value. A live range is defined as a write to a register followed by all the uses of that register until the next write.
An edge between two nodes indicates that those two live ranges interfere with each other because their lifetimes overlap. In other words, they are both simultaneously active at some point in time, so they must be assigned to different registers.

The resulting graph is thus called an interference graph.

Example of Register Allocation
a := c + d
e := a + b
f := e – 1
Let’s make the assumption that a and e die after use
The temporary variable a can be “reused” after the statement:
e := a + b
The same – Temporary e can be reuses after the statement: f := e – 1
Therefore, we can allocate a, e, and f all to one register (r1):
The resulting block of code is shown below with the variables allocated to registers.
r1 := r2 + r3
r1 := r1 + r4
r1 := r1 – 1
The value in a dead temporary variable is not needed for the rest of the computation
A dead temporary variable can therefore be reused

Steps to Perform Register Allocation
So the question is, ‘given a program code, how do we perform register allocation by graph coloration?’. The answer is, follow a five-step procedure as listed below:
Step 1: Draw the Control Flow Graph (CFG)
Step 2: Perform Liveness Analysis
Step 3: Draw the Register Interference Graph
Step 4: Perform Graph Coloration
Step 5: Allocate Registers Based on Colored Graph

Example
L1: a := b + c
d := -a
e := d + f
if(expression) then
f := 2 * e
else
b := d + e
e := e -1


end if
b := f + c
goto L1

Drawing the Control Flow Graph

The Control Flow Graph (cfg) is a graph that shows the flow of control in the program. A directed edge from on node to the other shows a branch from a part of the code to the other.

These branches are caused by the presence of control constructs in the program, like th if-else statement or loop statement

 

Perform Liveness Analysis
Liveness analysis is procedures to determine which set of variables are live at each point in the program.
– A variable is live at a particular point in the program if its value at that point will be used in the future (dead, otherwise). To compute liveness at a given point, we need to look at subsequent part of the program.

The result of the liveness analysis is given below

 

Draw the Register Interference Graph
The Register Interference graph is an undirected graph that shows the which variables are live at each point in time and which registers would interfere when allocated.
When formulated as a coloring problem, each node in the graph represents the live range of a particular value. A live range is defined as a write to a register followed by all the uses of that register until the next write. An edge between two nodes indicates that those two live ranges interfere with each other because their lifetimes overlap. In other words, they are both simultaneously active at some point in time, so they must be assigned to different registers.
A node is used to represent each variable
An edge between t1 and t2 if they are live simultaneously at some point in the program
Two temporaries can be allocated to the same register if there is no edge connecting them

Register Interference Graph

 

About the Register Interference Graph
Properties of Register Interference Graph
It extracts exactly the information needed to characterize legal register assignments
It gives a global (i.e., over the entire flow graph) picture of the register requirements
After RIG construction the register allocation algorithm is architecture independent

Deductions from the RIG
Variables a and f cannot be allocated to the same register since there is an edge connecting them
Variables a and b can be allocated the same register since there is no edge connecting them

Similarly, b and c cannot be allocated the same register while b and d can be allocated to the same register

Perform Graph Coloration

The coloration is performed by assigning same color to variables that can be allocated the same register as deduced from the register interference graph.

I would like to suggest you take more time to understand exactly how it works and also do the practical yourself. You can also view the video explanation here: Register Allocation Via Graph Coloration

Leave a comment below if this has helped you.

Thanks for reading!

Always visit www.kttpro.com