1 Crore+ students have signed up on EduRev. Have you? 
GENERATING CODE FROM DAGs
The advantage of generating code for a basic block from its dag representation is that from a dag we can easily see how to rearrange the order of the final computation sequence than we can start from a linear sequence of threeaddress statements or quadruples.
Rearranging the order
The order in which computations are done can affect the cost of resulting object code. For example, consider the following basic block:
t1 : = a + b
t2 : = c + d
t3 : = e  t2
t4 : = t1  t3
Generated code sequence for basic block:
MOV a , R0
ADD b , R0
MOV c , R1
ADD d , R1
MOV R0 , t1
MOV e , R0
SUB R1 , R0
MOV t1 , R1
SUB R0 , R1
MOV R1 , t4
Rearranged basic block:
Now t1 occurs immediately before t4.
t2 : = c + d
t3 : = e  t2
t1 : = a + b
t4 : = t1  t3
Revised code sequence:
MOV c , R0
ADD d , R0
MOV a , R0
SUB R0 , R1
MOV a , R0
ADD b , R0
SUB R1 , R0
MOV R0 , t4
In this order, two instructions MOV R0 , t1 and MOV t1 , R1 have been saved.
A Heuristic ordering for Dags
The heuristic ordering algorithm attempts to make the evaluation of a nod the evaluation of its leftmost argument. The algorithm shown below produces the ordering in reverse.
Algorithm:
1) while unlisted interior nodes remain do begin
2) select an unlisted node n, all of whose parents have been listed;
3) list n;
4) while the leftmost child m of n has no unlisted parents and is not a leaf do begin
5) list m;
6) n : = m
end
end
Example: Consider the DAG shown below
Initially, the only node with no unlisted parents is 1 so set n=1 at line (2) and list 1 at line (3). Now, the left argument of 1, which is 2, has its parents listed, so we list 2 and set n=2 at line (6). Now, at line (4) we find the leftmost child of 2, which is 6, has an unlisted parent 5. Thus we select a new n at line (2), and node 3 is the only candidate. We list 3 and proceed down its left chain, listing 4, 5 and 6. This leaves only 8 among the interior nodes so we list that. The resulting list is 1234568 and the order of evaluation is 8654321.
Code sequence:
t8 : = d + e
t6 : = a + b
t5 : = t6  c
t4 : = t5 * t8
t3 : = t4  e
t2 : = t6 + t4
t1 : = t2 * t3
This will yield an optimal code for the DAG on machine whatever be the number of registers.
Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 