DAG for Register Allocation in Compilers

Estudies4you
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
DAG for Register Allocation in Compilers,code generation in compilers,jntuh compiler deisign lecture notes pdf,jntu compiler design notes pdf unitwise,phases of compilation,jntuh r15 compiler design syllabus,jntuh r16 compiler design syllabus pdf,estudies4you,labeling algorithm in code generation

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:              
DAG for Register Allocation in Compilers,code generation in compilers,jntuh compiler deisign lecture notes pdf,jntu compiler design notes pdf unitwise,phases of compilation,jntuh r15 compiler design syllabus,jntuh r16 compiler design syllabus pdf,estudies4you,labeling algorithm in code generation


To Top