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
- All internal nodes store operator values
- External or leaf nodes are identifiers or variable names or constants
Algorithm for Construction of DAG
There are three possible cases to
construct DAG on three address code:
Case 1: x = y op z
Case 2: x = op y
Case 3: x = y
DAG can be constructed as follows:
STEP 1:
If y is undefined then create a
node with label y. Similarly create a node with label 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.
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.
Example:
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 *.
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 *.
Step 4
For fourth statement b = e, append
b to node e.
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 +
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 +.
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
