SUBJECT CODE

TYPE THE SUBJECT NAME HERE

UNIT NO 5
CODE OPTIMIZATION

5.3 DAG

III VI
20CSPC602
COMPILER DESIGN
 20CSPC602
COMPILER DESIGN

DAG

DAG Representation
● DAG stands for Directed Acyclic Graph
● Syntax tree and DAG both, are graphical representations. Syntax tree does not find the
common sub expressions whereas DAG can
● Another usage of DAG is the application of optimization technique in the basic block
● To apply optimization technique on basic block, a DAG is a constructed three address
code which is the output of an intermediate code generation

Characteristics of DAG are:

● All internal nodes store operator values
● External or leaf nodes are identifiers or variable names or constants
 20CSPC602
COMPILER DESIGN

DAG
DAG representation for basic blocks

A DAG for basic block is a directed acyclic graph with the following labels on nodes:

1. The leaves of graph are labeled by unique identifier and that identifier can be variable

names or constants.

2. Interior nodes of the graph is labeled by an operator symbol.

3. Nodes are also given a sequence of identifiers for labels to store the computed value.

● DAGs are a type of data structure. It is used to implement transformations on basic

blocks.

● DAG provides a good way to determine the common sub-expression.

● It gives a picture representation of how the value computed by the statement is used in

subsequent statements.
 20CSPC602
COMPILER DESIGN

DAG

Algorithm for construction of DAG

Input:It contains a basic block

Output: It contains the following information:

● Each node contains a label. For leaves, the label is an identifier.

● Each node contains a list of attached identifiers to hold the computed values.

1. Case (i) x:= y OP z

2. Case (ii) x:= OP y

3. Case (iii) x:= y

 20CSPC602
COMPILER DESIGN

DAG
DAG can be constructed as follows:
STEP 1:
If y operand is undefined then create node(y).
If z operand is undefined then for case(i) create node(z).

STEP 2:
For case 1, create a node with label op whose left child is node y, and node z will be the right
child. Also, check for any common sub expressions. For case 2, determine if a node is
labelled op. such node will have a child node y. for case 3 node n will be node y.

For case(i), create node(OP) whose right child is node(z) and left child is node(y).
For case(ii), check whether there is node(OP) with one child node(y).
For case(iii), node n will be 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 step 2.
 20CSPC602
COMPILER DESIGN

DAG

Consider the following three address code statements.

a=b*c
d=b
e=d*c
b=e
f=b+c
g=f+d
Step 1
Consider the first statement, i.e., a = b * c. Create a leaf node with label b and c as left and
right child respectively and parent of it will be *. Append resultant variable a to the node *.
 20CSPC602
COMPILER DESIGN

DAG

Step 2
For second statement, i.e., d = b, node b is already created. So, append d to this node.

Step 3
For third statement e = d * c, the nodes for d, c and * are already create. Node e is not
created, so append node e to node *.
 20CSPC602
COMPILER DESIGN

DAG

Step 3
For third statement e = d * c, the nodes for d, c and * are already create. Node e is not
created, so append node e to node *.

Step 4
For fourth statement b = e, append b to node e.
 20CSPC602
COMPILER DESIGN

DAG

Step 5
For fifth statement f = b + c, create a node for operator + whose left child b and right child c
and append f to newly created node +.
 20CSPC602
COMPILER DESIGN

DAG

Step 6
For last statement g = f + d, create a node for operator + whose left child d and right child f
and append g to newly created node +.
 20CSPC602
COMPILER DESIGN

DAG

DAG Applications:
● Determines the common sub expressions
● Determines the names used inside the block, and the names that are computed outside
the block
● Determines which statements of the block could have their computed value outside the
block
● Code may be represented by a DAG describing the inputs and outputs of each of the
arithmetic operations performed within the code; this representation allows the compiler
to perform common subexpression elimination efficiently
● Several programming languages describe systems of values that are related to each
other by a directed acyclic graph. When one value changes, its successors are
recalculate; each value is evaluated as a function of this predecessors in the DAG
 20CSPC602
COMPILER DESIGN

DAG

1. Directed Acyclic Graph (DAG) with Examples | Compiler Design | GATE CS | Ravindrababu Ravula
2. DAG representation of a basic block||construction of dag from basic blocks
3. Directed Acyclic Graph (DAG) Examples | Compiler Design | Lec-57 | Bhanu Priya
4. Directed Acyclic Graph(DAG)3
 20CSPC602
COMPILER DESIGN

Thank You