Directed Acyclic Graph Representation of basic blocks

Directed Acyclic Graph Representation of basic blocks is the most important topic of compiler design.This will help for student studying in master degree in computer science.

1. Seminar on Principles of Compiler Design “Directed Acyclic Graph Representation of basic blocks” Presented By: Mohd Vaseem Akaram ID: 17370206 Presented To: Ms. Nivetha Ma'am Dept of Computer Science

2. In compiler design, a directed acyclic graph (DAG) is on abstract syntax tree(AST) with a unique node for each value. OR A directed acyclic graph(DAG) is a directed graph that contains no cycles. Definitions

3. DAG is useful data structure for implementing transformation on basic blocks. A basic block can optimized by the construction of DAG. A DAG can be constructed for a block and certain transformations such as common sub-expression elimination and dead code elimination applied for performance the local optimization. To apply the transformation on basic block, a DAG is constructed from three address code. Use of DAG for optimizing basic blocks

4. The DAG is Used In: Determine the common sub expression (Expression computed more than one). Determine which names are used in block and computed outside the block. Determine which statements of the block could their computed value. Applications of DAG

5. Rule 1: In a DAG Leaf node represent identifiers, names or constants. Interior node represent operators. Rule 2: While constructing DAG, there is a check made to find if there is on existing node with the same children. A new node is created only when such a node doesn't exist This action allow us to detect common sub expression and eliminate the re computation of the same. Rule 3: The assignment of the from x:= must not be performed until and unless it is a must. Rules of the constructing DAG

6. Problem 1: Construct DAG for the given expression ( a+b ) * ( a+b+c ) Solution: Three address code for the given expression. t1= a+b t2=t1+c t3=t1*t2 The DAG is: Problems

7. From the constructed DAG, we observed that the common sub expression ( a+b ) is translated into a single node in the DAG. The computation is carried out only once and stored in the identifier t1 and reused later. This illustrates how the DAG construction scheme identifies the common sub expression and helps in elimination its re-computation later. Explanation

8. Problem 2: Construct DAG for the given expression ( ( ( a+a ) + ( a+a ) ) + ( ( a+a ) + ( a+a ) ) ) Solution: DAG for this Expression is-

9. Problem 3: Construct DAG for the given expression a = b * c d = b e = d * c b = e f = b + c g = f + d Solution: Step 1: Step 2:

10. Step 3: Step 4: Step 5: Step 6:

11. Thank You! 