Constructing a DAG for a Basic Block with Variable Redefinitions

To construct the DAG for a basic block, you typically represent each statement as a node and draw edges to express data dependencies between the definitions of values and the uses of those values. Key dependency notions include true (flow) dependence and anti-dependence; together they guide correct ordering constraints. 2

For the basic block:

the challenge is the redefinition of $b$ in the third statement. That means the uses of $b$ in statement 2 must depend on the original $b$ (from before the block), while the computation in statement 3 defines a new $b$ that is not used later within the block. Correct DAG construction therefore distinguishes “versions” of $b$ (via conceptual SSA-style renaming) so that edges reflect the proper source of each used value. 2

Key definitions for DAG construction

• basic block: we assume control flow is fixed, so dependencies are about values, not branch decisions.
• node: each assignment becomes a node.
• use and definition: edges connect definitions to uses.
• SSA renaming: often done conceptually to handle reassignments like $b=b*c$.

A compact way to think about the DAG is:

1. Create a node for each assignment.
2. For each operand on the RHS, connect from the node (or input) that produces that exact value version.

DAG construction with value renaming

Let:

• Node $N1$: $d \leftarrow b * c$
• Node $N2$: $e \leftarrow a + b$
• Node $N3$: $b \leftarrow b * c$ (redefines $b$)
• Node $N4$: $a \leftarrow e - d$

Conceptually rename:

• $b$ used in $N1$ and $N2$ is $b_0$ (incoming $b$ to the block)
• $b$ defined by $N3$ is $b_1$

Also treat $a$ and $c$ as block inputs feeding the first uses:

• $a$ input is $a_0$
• $c$ input is $c_0$

Now the true dependencies are:

• $N1$ uses $b_0$ and $c_0$, defines $d$
• $N2$ uses $a_0$ and $b_0$, defines $e$
• $N3$ uses $b_0$ and $c_0$, defines $b_1$
• $N4$ uses $e$ and $d$, defines $a$ (new value $a_1$)

Thus, edges are from the definition of each operand to each use:

• From input $b_0$ to $N1$, $N2$, $N3$
• From input $c_0$ to $N1$, $N3$
• From input $a_0$ to $N2$
• From $N1$ (defines $d$) to $N4$ (uses $d$)
• From $N2$ (defines $e$) to $N4$ (uses $e$)

A correct DAG reflects only these value-producing dependencies (and not “schedule” dependencies that would be implied by anti/output dependence unless you’re building a dependence graph for reordering). The usual DAG for expression evaluation in a basic block is centered on true data dependencies. 2

Visual DAG (true data dependence)