DAG Representation in Compiler Design

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

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

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.