The dag representation of basic blocks

Seminar on PCD

1. The Dag Representation of Basic Blocks PRESENTED BY A.SHABEEN TAJ BP150518

2. CONTENTS Introduction A DAG with following labels on nodes Dag Construction Constructing a DAG Applications of Dags Arrays, Pointers and Procedure calls Rules

3. Introduction : Directed Acyclic Graphs ( dags ) are useful data structures for implementing transformations on basic blocks. A dag gives a picture of how the value computed by each statement in a basic block is used in subsequent statements of the block. Constructing a dag from three- address statements is a good way of determining common sub expressions within a block, determining which names are used inside the block but evaluate outside the block, and determining which statements of the block have their computed value outside the block.

4. A dag with following labels on nodes: Levels are labeled by unique identifiers, either variable names or constants. Interior nodes are labeled by an operator symbol. Nodes are also optionally given by a sequence of identifiers for labels. The intention is that interior nodes represent computed values, and the identifiers labeling a node are deemed to have that value. It is important not to confuse dags with flow graphs. Each node of a flow graph can be represented by a dag, since each node of the flow graph stands for a basic block.

5. Dag Construction: To construct a dag: When we see a statement of the form x:= y+z , Y and z – leaves / interior nodes. When we create labeled + => has two children Y – left child and z- right child and its label is x. If the another node has same value y+z , instead of adding new node, existing node can be used as label x.

6. Two details should be mentioned: First, if x had previously labeled some other node, remove that label, since the “current” value of x is the node created. Second, for assignment x:=y, do not create a new node, but append x to the list of names on the node for the “current” value of y.

7. Constructing a dag: Input: A basic block Output: It has following information,] A label for each node. For leaves label is an identifier (constants permitted) and for interior nodes, an operator symbol. For each node a list of attached identifiers(constants not permitted). Method: Data structures are available to create nodes with one or two children distinguishing left and right. To create a linked list of attached identifiers for each node.

8. The dag construction has the following process: Initially assume, no nodes and nodes is undefined for all arguments. Suppose “current” three address statements ( i ) x:= y op z (ii) x:=op y (iii) x:=y. Treat a relational operator like if i <=20 goto case ( i ), with x undefined. If node(y) is undefined, create a leaf labeled y, and let node(y) be this node. In case( i ), If node(z) is undefined, create a leaf labeled z, and let the leaf node(z).

9. 2. In case ( i ), determine if there is a node labeled op, whose leaf child is node(y) and right child is node(z). If not, create such a node and n be the node found or created. In case (ii), determine whether ther is node labeled op, whose lone child is node(y). If not, create such a node and n be the node found or created. In case(iii), let n be node(y) 3. Delete x from the list of attached identifiers for node (x). Append x to list of attached identifiers for node n found in (2) and set node(x) to n.

10. Applications of dags : Automatically detect common sub expressions. Can determine which identifiers have their values used in the block. Can determine which statements compute value that could be used outside the block.

11. Example:9.10 Let us reconstruct a basic block from the dag of fig 9.16, ordering nodes in the same order as they were created. So the first reconstructed statement is, t1:=4*I Second, statement constructed as, t2:=a[t1] The next is labeled as t4, t4:=b[t1]

12. Then, t5 is constructed as, t5:=t2*t4 For label t6 and prod, like t3, temporary t6 disappears. So the generated statement is, prod:=prod+t5 Similarly, choose I rather than t7 to carry the vale i+1. The last two statements generated are, i :=i+1 if i <=20 goto (1) Reduced ten statements to seven using common sub expression (dag advantage) and by eliminating unnecessary assignments.

13. Arrays, Pointers and Procedure Calls: Consider the block: X:=a[ i ] a[j]:=y z:=a[ i ] (9.5) Construct dag a[ i ] would become common sub expression and optimized as X:=a[ i ] z:=x a[j]:=y (9.6) However, (9.5)and (9.6) compute different values for z in case i =j and y!=a[ i ].

14. Rules: Let us introduce certain edges n->m in dag that do not indicate that m is an argument of n, but rather that evaluation of n must follow evaluation of m in any computation of the dag. The rules are: Any evaluation of or assignment to an element of array a must follow previous assignment to an element of that array if there is one. Any assignment to an element of array a must follow previous evaluation of a.

15. 3. Any use of any identifier must follow the previous procedure call or indirect assignment through a pointer if there is one. 4. Any procedure call or indirect assignment through a pointer must follow all previous evaluations of any identifier. That is, when reordering code, uses of an array a may not cross each other, and no statement may cross a procedure call or an assignment through a pointer.

16. Any Queries: ???

17. Thank you