DAG representation of basic blocks
DAG representation is an important topic of the Compiler Design.
freestudy9 comes with new post related to DAG representation.
- The directed acyclic graph is used to apply transformations to the basic block.
- A DAG gives a picture of how the value computed by each statement in a basic block used in subsequent statements of the block.
- To apply the transformations on a basic block a DAG is constructed from three address statement.
- A DAG can be constructed for the following type of labels on nodes,
1. Leaf nodes are labeled by identifiers or variable names or constants. Generally, leaves represent rr-values.
2. Interior nodes store operator values.
3. Nodes are also optionally given a sequence of identifiers for a label.
- The DAG and flow graphs are two different pictorial representations. Each node of the flow graph can be represented by DAG because each node of the flow graph is a basic block.
Example: sum = 0;
for (i=0;i< = 10;i++)
sum = sum+a[t1];
The three address code for above code is
sum :=0 B1
2. t1 := 4*i
3. t2:= a[t1]
4. t3:= sum+t2
5. sum := t3
6. t4 := i+1;
7. i:= t4
8. if i<=10 goto (3)
Algorithm for Construction of DAG: DAG representation
- We assume the three address statement could of following typestyles,
Case (i) x:=y op z
Case (ii)x:=op y
Case (iii) x:=y
With the help of the following step, the DAG can be constructed.
Step 1: If y is undefined then create a node(y). Similarly, if z is undefined create a: node(z)
Step 2: For the case(i) create a node(op) whose left child is node(y) and node(z) will be) the right child. Also, check for any common subexpressions. For the case(ii) determine whether is a node labeled op, such node will have a child node(y). In case(iii) node n win be node(node(y).
Step 3: Delete x from list of identifiers for node(x). Append x to the list of attached identifiers for node n found in 2.
Applications of DAG (DAG representation)
The DAGs are used in,
1. Determining the common sub-expressions.
2. Determining which names are used inside the block and computed outside the block.
3. Determining which statements of the block could have their computed value outside the block.
4. Simplifying the list of quadruples by elimination the common sub-expressions and not eliminating expressions performing the assignment of form x:=y unless and until it is a must.