DAG for Register Allocation in Compilers

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:              

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.