DAG RepresentationDAG stands for Directed Acyclic GraphSyntax tree and DAG both, are graphical representations.
Syntax tree does not find the common sub expressions whereas DAG canAnother usage of DAG is the application of optimization technique in the basic blockTo apply optimization technique on basic block, a DAG is a constructed three address code which is the output of an intermediate code generationCharacteristics of DAG are:All internal nodes store operator valuesExternal or leaf nodes are identifiers or variable names or constantsAlgorithm for Construction of DAGThere are three possible cases to construct DAG on three address code:Case 1: x = y op zCase 2: x = op yCase 3: x = yDAG 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 + dStep 1Consider 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 *.
Best services for writing your paper according to Trustpilot
Step 2For second statement, i.e., d = b, node b is already created. So, append d to this node.Step 3For 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 4For fourth statement b = e, append b to node e.Step 5For 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 6For 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 expressionsDetermines the names used inside the block, and the names that are computed outside the blockDetermines which statements of the block could have their computed value outside the blockCode 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 efficientlySeveral 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
