DAG for Register Allocation
Code generation
from DAG is much simpler than the linear sequence of three address code
With the help of
DAG one can rearrange sequence of instructions and generate and efficient code
There exist
various algorithms which are used for generating code from DAG. They are:
Code Generation
from DAG:-
Rearranging
Order
Heuristic
Ordering
Labeling
Algorithm
Rearranging Order
These address
code’s order affects the cost of the object code which is being generated
Object code with
minimum cost can be achieved by changing the order of computations
Example:
t1:= a + b
t2:= c – d
t3:= e + t2
t4:= t1 + t3
For the
expression (a+b) + (e+(c-d)), a DAG can be constructed for the above sequence
as shown below
The code is thus
generated by translating the three address code line by line
MOV a, R0
ADD b, R0
MOV c, R1
SUB d, R1
MOV R0, t t1:= a+b
MOV e, R0 R1 has c-d
ADD R0, R1 /* R1 contains e + (c – d)*/
MOV t1, R0 /R0 contains a + b*/
ADD R1, R0
MOV R0, t4
Now, if the
ordering sequence of the three address code is changed
t2:= c - d
t3:= e + t2
t1:= a + b
t4:= t1 + t3
Then, an
improved code is obtained as:
MOV c, R0
SUB D, R0
MOV e, R1
ADD R0, R1
MOV a, R0
ADD b, R0
ADD R1, R0
MOV R0, t4
Heuristic Ordering
The algorithm
displayed below is for heuristic ordering. It lists the nodes of a DAG such
that the node’s reverse listing results in the computation order.
{
While unlisted interior nodes remain
do
{
select an unlisted node n, all of whose parents have been
listed;
List n;
While the leftmost child ‘m’ of ‘n’ has no unlisted parents and
is not a leaf
do
{
/*since na was just listed, surely m is not yet listed*/
}
{
list m
n =m;
}
}
order = reverse of the order of listing of nodes
}
Labeling Algorithm
Labeling algorithm deals with the tree representation of a
sequence of three address statements
It could similarly be made to work if the intermediate code
structure was a parse tree. This algorithm has two parts:
- The first part labels each node of the tree from the bottom up,
with an integer that denotes the minimum number of registers required to
evaluate the tree, and with no storing of intermediate results
- The second part of the algorithm is a tree traversal that
travels the tree in an order governed by the computed labels in the first
part, and which generates the code during the tree traversal
if n is a leaf then
if n
is leftmost child of its parents then
Label(n)
= 1
else
label(n) = 0
else
{
/*n is an interior node*/
let n1, n2, …..,nk be the
children of ordered by label,
so label(n1) >= label(n2)
>= … >= label(nk);
label(n) = max (label (ni) + i –
1)
}
Example:
