Directed Acyclic Graphs (DAGs): Optimizing Basic Blocks in Compilers

Learn how Directed Acyclic Graphs (DAGs) are used for optimizing basic blocks in compiler design. This guide explains how DAGs represent computations, enabling efficient identification of common subexpressions and other optimization opportunities for improved code generation.

Directed Acyclic Graphs (DAGs) for Basic Block Optimization

Understanding DAGs in Compiler Design

In compiler design, a directed acyclic graph (DAG) is a graph representation of a basic block (a sequence of code with one entry and one exit point). DAGs are acyclic (no cycles) and directed (edges show the flow of computation). They are used in compiler optimization because they provide a clear, structured representation of the computations within a basic block, making it easier to identify and apply various optimization techniques, such as common subexpression elimination.

Structure of a DAG for Basic Blocks

In a DAG representing a basic block:

  • Leaf nodes represent variables or constants.
  • Interior nodes represent operators.
  • Each node stores the computed value.

This makes it straightforward to see the flow of data and the dependencies between different computations. The DAG's structure is very useful for identifying opportunities to optimize the code.

Algorithm for Constructing a DAG

Building a DAG from three-address code involves these steps:

  1. Input: A basic block (a sequence of three-address statements).
  2. Output: A DAG with nodes labeled by identifiers or operators, and each node containing a list of identifiers representing the computed value.
  3. Three Cases: The algorithm handles three cases:
    1. Binary operation: x := y OP z
    2. Unary operation: x := OP y
    3. Assignment: x := y
  4. Processing Steps:
    1. Check if operands are undefined; create nodes if necessary.
    2. For binary operations, create an operator node with operands as children. For unary operations, reuse an existing operator node if possible; otherwise, create one. For assignments, simply use the operand node.
    3. Update the target node (x) to point to the new or reused node. Remove x from the list of identifiers and add it to the list of identifiers associated with the appropriate node.

Example: DAG Construction

Consider this three-address code:

Three-Address Code

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

The resulting DAG would show how intermediate results (like 4 * i) are reused, highlighting opportunities for optimization.

Example DAG