Dag representation of basic blocks

PCD subject

1. DAG-REPRESENTATION OF BASIC BLOCKS V.JOTHI LAKSHMI

2. DAG representation of basic blocks Useful data structures for implementing transformations on basic blocks Gives a picture of how value computed by a statement is used in subsequent statements Constructing DAG from 3 address statements is good way of determining common sub-expressions A dag for a basic block has following labels on the nodes Leaves are labeled by unique identifiers, either variable names or constants Interior nodes are labeled by an operator symbol Nodes are also optionally given a sequence of identifiers for labels 2

3. DAG for basic block

4. DAG representation: example t 1 := 4 * i t 2 := a[t 1 ] t 3 := 4 * i t 4 := b[t 3 ] t 5 := t 2 * t 4 t 6 := prod + t 5 prod := t 6 t 7 := i + 1 i := t 7 if i <= 20 goto (1) 4 + prod * [ ] [ ] * i 4 b a + 1 20 <= t 1 t 4 t 5 t 6 t 7 (1) t 3 t 2 prod i

5. DAG Construction Construct a dag for a basic block. Process each statement of the block inturn . Statement of the form x:= y+z Look for the nodes that represent the “current” values of y and z. These could be leaves/interior nodes of dag If y & z has been evaluated by previous statements of block. We create a node labeled + and give it two children Left –node for y right- node for z 5

6. DAG Algorithm Input - basic block. Output - label for each node. label is an identifier for leaves. label is an operator symbols for interior nodes. each node has list of identifiers. Method - create nodes with one or two children left & right. create linked list of attached identifiers for each node. maintain all identifiers for which a node is associated. node (identifier) represents value that identifier has the current point in dag construction process. Symbol table record for identifier- indicate the value of node(identifier). 6

7. DAG Algorithm Given a function node(identifier) – it returns the node currently associated with the identifier. Statement types ( i ) x := y op z (ii) x := op y (iii) x := y If node(y ) is undefined then create a leaf labeled y and this is now node(y ) in case of x = y op z ; do the same for z . Determine if there is a node labeled “ op ” with node(y) & node(z) as the left and right children in case of x = y op z . Determine whether there is a node labeled op ,whose lone child is node(y) , let n be node(y). 7

8. Code Generation from DAG S 1 = 4 * i S 2 = addr (A)-4 S 3 = S 2 [S 1 ] S 4 = 4 * i S 5 = addr (B)-4 S 6 = S 5 [S 4 ] S 7 = S 3 * S 6 S 8 = prod+S 7 prod = S 8 S 9 = I+1 I = S 9 If I <= 20 goto (1) 8 S 1 = 4 * i S 2 = addr (A)-4 S 3 = S 2 [S 1 ] S 5 = addr (B)-4 S 6 = S 5 [S 4 ] S 7 = S 3 * S 6 prod = prod + S 7 I = I + 1 If I <= 20 goto (1)

9. Rearranging Order Of The Code Consider following basic block t 1 = a + b t 2 = c + d t 3 = e –t 2 X = t 1 –t 3 and its DAG 9 - + a b - e + c d X t 3 t 2 t 1

10. Application of DAG DAGs are useful for: Removing common local sub-expressions. Renaming temporaries. Finding names used inside the block but evaluated outside. Finding statements in the block that could have their computed values used outside the block. Statements that can be reordered (or executed in parallel ). 10

11. Arrays x :=a[ i ] x :=a[ i ] a[j] :=y  (9.5) z :=x  (9.6) z :=a[ i ] a[j] :=y Both compute different values for z in case i =j and y!=a[ i ] .When we assign to an array a , we may be changing the r-value of expression a[ i ] ,even though a and i do not change . It is therefore necessary that when processing an assignment to array a , we kill all nodes labeled [] ,whose left arg is + or – constant.

12. DAG For A Sequence Of Array Assignments

13. POINTERS *p :=w , where p is pointer. If we do not know what p might point to , every node currently in the DAG being built must be killed in the sense above. If p could only point to r or s , then only node(r) and node(s) must be killed.

14. PROCEDURE CALLS A procedure call in a basic block kills all nodes , since in the absence of knowledge about the called procedure , we must assume that any variable may be changed as a side effect.

15. THANK YOU