Question

Explain how a basic block is represented using dag?

Answer 1

THE DAG REPRESENTATION FOR BASIC BLOCKS
• A DAG for a basic block is a directed acyclic graph with the following labels on nodes:

1. Leaves are labeled by unique identifiers, either variable names or constants.
2. Interior nodes are labeled by an operator symbol.

3. Nodes are also optionally given a sequence of identifiers for labels to store the computed values.

• DAGs are useful data structures for implementing transformations on basic blocks.
• It gives a picture of how the value computed by a statement is used in subsequent statements.
• It provides a good way of determining common sub - expressions.