Scribd
Upload
414 views8 pages

DAG - Directed Acyclic Graph

1. A DAG (Directed Acyclic Graph) is a representation used to assist in code reordering. Nodes represent operations and edges represent dependences. 2. DAGs are useful for removing common subexpressions, renaming temporaries, and finding variable uses and definitions to enable reordering or parallelization. 3. DAG construction processes statements and creates nodes for variables, operators, and results, and links them to represent dependencies.

Uploaded by

Ms.R.Thillaikarasi CSE Department
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
414 views8 pages

DAG - Directed Acyclic Graph

1. A DAG (Directed Acyclic Graph) is a representation used to assist in code reordering. Nodes represent operations and edges represent dependences. 2. DAGs are useful for removing common subexpressions, renaming temporaries, and finding variable uses and definitions to enable reordering or parallelization. 3. DAG construction processes statements and creates nodes for variables, operators, and results, and links them to represent dependencies.

Uploaded by

Ms.R.Thillaikarasi CSE Department
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 8

DAG

DAG – Directed Acyclic Graph


A representation to assist in code reordering.
+ Nodes are operations
+ Edges represent dependences
Nodes are labeled as follows:
1.Leaves with variables or constants – subscript 0 is used to
distinguish initial value of the variable from other values.
2.Interior nodes with operators and list of variables whose
values are computed by the node.

1
DAGs Contd..
DAGs are useful for:
1.Removing common local sub-expressions.
2.Renaming temporaries.
3.Finding names used inside the block but evaluated
outside.
4.Finding statements in the block that could have their
computed values used outside the block.
5.Statements that can be reordered (or executed in
parallel).

2
DAG Construction
Given a function node(identifier) – it returns the node
currently associated with the identifier.
Process one statement at a time as follows:
Statement types: x = y op z; x = op y; x = y;
1.If node(y) is undefined then create a leaf labeled yo and
this is now node(y) in case of x = y op z; do the same for z.
2.Determine if there is a node labeled “op” with node(y) &
node(z) as the left and right children in case of x = y op z.

3
DAG Construction Contd..
2 Contd. In case of x = op y, check if there is a node
labeled “op” with single child node(y).
If not, create such a node.
Let the node found or created by n.
3. Delete x from the list of identifiers attached to
node(x) & append x to the list of identifiers
attached to node n.
Set node(x) to n.

4
Example of DAG Construction

T1 = J * 2
T2 = X[T1]
T3 = T2 + N
T4 = J * 2
T5 = Y[T4]
T6 = T5 + T3
ANS = T6
T7 = J+ 1
J = T7
ANS = J
If J<10 goto L
5
Code Reordering
DAG captures all legal re-orderings. Which ordering should
we select?
Try to place computation & use of a value next to each
other so that the register used by the value is freed
immediately.
Next we will look at a heuristic that attempts, as far as
possible, to make the evaluation of a node immediately
follow the evaluation of the leftmost argument.

6
Code Reordering Contd..
Algorithm: List nodes in reverse order.

While unlisted interior nodes remain Do


select an unlisted node n, all of whose parents have been listed
list n
While leftmost child m of n has no unlisted parents and is not a leaf Do
list m
n=m
End while
End while

7
Example

You might also like