# Dag Representation Of A Basic Block Allows

0
593

## Dag Representation Of A Basic Block Allows

Dag Representation Of A Basic Block Allows is the easiest topic in computer science, In this article, you will learn easily Dag Representation Of A Basic Block Allows. In this tutorial, we are going to learn about Dag Representation Of A Basic Block Allows.

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

• The graph’s leaves are labelled with a unique identifier, which can be variable names or constants.
• An operator symbol is used to label the graph’s interior nodes.
• A sequence of identifiers for labels is also provided to nodes to store the computed value.
• Data structures known as DAGs are a type of data structure. It’s used to perform simple block transformations.
• DAG is a useful tool for determining the generic sub-expression.
• It shows how the meaning computed by the argument is used in subsequent statements in a visual representation.

## 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.
``````Case (i) x:= y OP z
Case (ii) x:= OP y
Case (iii) x:= y  ``````

Method of Dag Representation Of A Basic Block Allows

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(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).

Output:

For node(x) delete x from the list of identifiers. Append x to the attached identifiers list for the node n found in step 2. Finally set node(x) to n.

Example of Dag Representation Of A Basic Block Allows

``````S1:= 4 * i
S2:= a[S1]
S3:= 4 * i
S4:= b[S3]
S5:= s2 * S4
S6:= prod + S5
Prod:= s6
S7:= i+1
i := S7
if i<= 20 goto (1)   ``````

Basic block – Wikipedia