Generating code from dags

5th chapter

1. GENERATING CODE FROM DAGs Presented by INDUMATHI.A (BP150517)

2. 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 starting from a linear sequence of three-address statements or quadruples

3. Cont… t1 := a + b t2 := c + d t3 := e - t2 t4 := t1 - t3 (1) MOV a, R0 (2) ADD b, R0 (3) MOV c, R1 (4) ADD d, R1 (5) MOV R0, t1 (6) MOV e, R0 (7) SUB R1, R0 (8) MOV t1, R1 (9) SUB R0, R1 (10) MOV R1, t4 - + - + a b e c d t1 t2 t3 t4

4. Rearranging the Order t2 := c + d t3 := e - t2 t1 := a + b t4 := t1 - t3 (1) MOV c, R0 (2) ADD d, R0 (3) MOV e, R1 (4) SUB R0, R1 (5) MOV a, R0 (6) ADD b, R0 (7) SUB R1, R0 (8) MOV R0, t4 - + - + a b e c d t1 t2 t3 t4

5. A Heuristic ordering for Dags The heuristic ordering algorithm attempts to make the evaluation of a node immediately follow the evaluation of its leftmost argument.

6. Node Listing Algorithm while unlisted interior nodes remain do begin 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 begin list m ; n := m ; end end

7. Example: 3 2 1 - + * a b c + d e 6 - + * 4 5 7 t7 := d + e t6 := a + b t5 := t6 - c t4 := t5 * t7 t3 := t4 - e t2 := t6 + t4 t1 := t2 * t3

8. Optimal ordering for trees Label each node of the tree bottom-up with an integer denoting fewest number of registers required to evaluate the tree with no stores of immediate results Generate code during a tree traversal by first evaluating the operand requiring more registers

9. The Labeling Algorithm if n is a leaf then if n is the leftmost child of its parent then label ( n ) := 1 else label ( n ) := 0 else begin let n 1 , n 2 , …, n k be the children of n ordered by label so that label ( n 1 )  label ( n 2 )  …  label ( n k ); label ( n ) := max 1 i  k ( label ( n i ) + i - 1) end

10. An Example: label ( n ) = max( l 1, l 2), if l 1  l 2 l 1 + 1, if l 1 = l 2 t1 t4 t2 a b c t3 d e 1 2 1 2 1 1 1 For binary interior nodes:

11. Code Generation From a Labeled Tree Use a stack rstack to allocate registers R0, R1, …, R( r -1) The value of a tree is always computed in the top register on rstack The function swap ( rstack ) interchanges the top two registers on rstack Use a stack tstack to allocate temporary memory locations T0, T1, ...

12. Cases Analysis op n 1 n 2 op n 1 n 2 op n 1 n 2 label ( n 1 ) < label ( n 2 ) label ( n 2 )  label ( n 1 ) both labels  r op n 1 n 2 n name name

13. The Function gencode /* case 1 */ begin let name be the operand represented by n 2 ; gencode ( n 1 ); print op || name || ',' || top ( rstack ) end /* case 2 */ begin swap ( rstack ); gencode ( n 2 ); R := pop ( rstack ); gencode ( n 1 ); print op || R || ',' || top ( rstack ); push ( rstack , R ); swap ( rstack ); end

14. Cont…. /* case 3 */ begin gencode ( n 1 ); R := pop ( rstack ); gencode ( n 2 ); print op || R || ',' || top ( rstack ); push ( rstack , R ); end /* case 4 */ begin gencode ( n 2 ); T := pop ( tstack ); print 'MOV' || top ( rstack ) || ',' || T ; gencode ( n 1 ); push ( tstack , T ); print op || T || ',' || top ( rstack ); end

15. Example gencode (t4) [R1, R0] /* 2 */ gencode (t3) [R0, R1] /* 3 */ gencode (e) [R0, R1] /* 0 */ print MOV e, R1 gencode (t2) [R0] /* 1 */ gencode (c) [R0] /* 0 */ print MOV c, R0 print ADD d, R0 print SUB R0, R1 gencode (t1) [R0] /* 1 */ gencode (a) [R0] /* 0 */ print MOV a, R0 print ADD b, R0 print SUB R1, R0 t1 t4 t2 a b c t3 d e 1 2 1 2 1 1 1

16. Multiregister Operations Some operations like multiplication, division, or a function call normally require more than one register The labeling algorithm needs to ensure that label ( n ) is always at least the number of registers required by the operation label ( n ) = max( 2 , l 1, l 2), if l 1  l 2 l 1 + 1, if l 1 = l 2

17. Algebraic Properties + T 1 + T 1 1 l max(2, l ) l l + T 1 T 4 + T 2 T 3 + T i 3 + T i 1 T i 2 + T i 4 + associative commutative largest commutative

18. Common Subexpressions Nodes with more than one parent in a dag are called shared nodes Optimal code generation for dags on both a one-register machine or an unlimited number of registers machine are NP-complete