Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 61 ยท Intermediate Code and Optimization

DAG Representation and Value Numbering

Represent a basic block as a directed acyclic graph to share common subexpressions, then learn local value numbering with constants and commutativity, with runnable code.

The local optimizations lesson removed repeated computations with a table keyed by operator and operands. This lesson looks at the two classical ways to do the same thing more systematically: build a directed acyclic graph (DAG) of the basic block, or number values with value numbering. They are two views of one idea, and both give you more than a single trick: common subexpressions, dead code, and the order in which values may be computed fall out from the same data structure.

A basic block is a straight-line stretch of code, so the order of the statements is clear and nothing jumps in or out. That makes it possible to reason about "the value computed by this expression" without worrying about control flow.

The idea: one node per value

In a syntax tree, an expression such as (p + q) * (p + q) has two separate copies of p + q. In a DAG, both uses point to the same node: if you have already computed this value, do not make another node for it.

flowchart BT
    p["p (entry value)"] --> S["+"]
    q["q (entry value)"] --> S
    S --> M["*"]
    S --> M
    M --> D["-"]
    r["r (entry value)"] --> D

The DAG for x = (p + q) * (p + q) - r. The + node has two parents and is computed once.

The DAG for a basic block has these parts:

  • Leaf nodes for the values that variables and constants have on entry to the block. They are labelled with the variable name (often written a0) or the constant.
  • Interior nodes for operations. Each has an operator and the nodes of its operands as children.
  • Labels attached to the interior nodes: the variables that currently hold that node's value.

Building the DAG

Process the statements in order. For a statement x = y op z:

  1. Find the node for y and the node for z: the node that y and z currently label, or a new leaf if the variable has not been seen yet.
  2. Look for an existing node with the same operator and the same children. If there is one, reuse it, otherwise create it. For commutative operators (+, *) the children may be in either order.
  3. Move the label x to this node. If x labelled another node, remove it from there: the variable no longer holds that old value.

The third step is what makes the DAG handle reassignment correctly. After a = c - t1, the name a points at a new node. A later a + b therefore builds a new node instead of wrongly sharing the earlier a + b, which used the old a.

Copies x = y just add the label x to the node of y. No code is needed for them.

What a DAG gives you

  1. Common subexpressions are detected, as above.
  2. Dead code becomes visible: an interior node whose labels are all temporaries and which no other node uses computes nothing anyone needs. If a node has no live variable among its labels, it can be dropped.
  3. A valid evaluation order: any topological order of the interior nodes (children before parents) is a correct way to compute the block. Different orders use different numbers of registers, so a code generator can pick a good one.
  4. Which variables are used in the block before being defined: they are the leaves.

To generate code back from the DAG, you walk the interior nodes in order. For each node that is still needed, you compute it into one of its live-on-exit labels (a variable that must keep the value after the block), or into a temporary if it has none. Remaining live labels get a copy.

A runnable DAG builder

The program builds the DAG of a seven-statement block, prints the nodes with their labels, regenerates the code for the variables that are live on exit, and checks that old and new code give the same results on 49 inputs.

Python Building a DAG and regenerating the block

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Study the node table. Nodes n2 and n5 each carry two labels: t1 and t2 both hold a + b, and d and e both hold b + a (the node stores sorted children, so b + a and a + b with the new a count as one). Node n6 computes c * c, labelled f, but f is not live on exit and nothing else uses it, so the regenerated code drops it. Seven statements became five.

Two caveats keep real implementations careful. First, a DAG cannot see through pointers and array elements: after *p = 5 any value loaded from memory may have changed, so nodes that depend on memory must be "killed" at stores and at calls. Second, you must compute an interior node before any variable it reads is overwritten. The program avoids that by emitting nodes in creation order. Production code generators check this explicitly when they reorder.

Value numbering

Value numbering gets the same result with a hash table instead of an explicit graph, which is quicker and easy to extend. Every distinct value in the block receives a number. Two expressions with the same value number are guaranteed to compute the same value.

Keep two tables: a map from each variable to the value number it currently holds, and a hash table from (operator, value number, value number) to a value number and a variable that holds it.

For x = y op z:

  1. Look up the value numbers vn(y) and vn(z); variables never seen before get a fresh number for their entry value, and constants get one number per constant value.
  2. Form the key (op, vn(y), vn(z)), with the two numbers sorted if op is commutative.
  3. If the key is in the table and some variable still holds that value, replace the statement with x = holder and give x the same value number. Otherwise, create a new value number, store it in the table with x as holder, and keep the statement.

The check "some variable still holds that value" is essential: if the variable that held the result was reassigned, using it would give the wrong answer. The next program shows this in the last statements.

Value numbering also extends cleanly:

  • Constant folding. If both operands have constant value numbers, compute the result at compile time and number it as a constant.
  • Copy propagation. a = t gives a the value number of t, so later computations treat them as the same value.
  • Algebraic identities. If an operand has the value number of the constant 0, then x + 0 has the value number of x. The same table lookups work for x * 1, x - x and others.
Python Local value numbering with folding and copies

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the trace and notice three things:

  • x = 4 + 5 and y = x * 2 are folded to constants because the value number of x is a known constant.
  • u = b + a reuses t = a + b. The commutative key (+, vn(a), vn(b)) is sorted, so the order of the operands does not matter.
  • After a = t, the variable a has a new value number (that of t), so v = a + b is a different computation and gets number 9. But w = t + b has the same key, since t and a hold the same value, and it is replaced by w = v. And at the end, t = 7 overwrites t, yet z = a + b is still found in v, because the table remembers v as the holder. The program checked that all variables end with the same values as the original block.

DAG or value numbering?

Aspect DAG Value numbering
Data structure Explicit graph with labels Hash table plus variable-to-number map
Finds common subexpressions Yes Yes
Constant folding and identities Possible, but awkward Natural
Dead code and evaluation order Directly visible in the graph Needs a separate pass
Typical use today Teaching, instruction selection Local optimization inside production compilers

Value numbering also extends beyond a single block. Superlocal numbering handles extended basic blocks, dominator-based numbering carries the table down the dominator tree, and global value numbering works on SSA form, where each name has exactly one definition and the "is the holder still valid?" question disappears.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the DAG of a basic block, what happens for the statement z = x + y when a node for x + y already exists?

    The DAG reuses the node, since it already represents that value. z just becomes another label, and z is removed from any node it labelled before.
  2. 2. After a = c - t1, the block contains d = a + b. Why does the DAG create a new + node instead of reusing an earlier a + b node?

    Moving the label a to the new node means the lookup for operand a finds a new value. The earlier a + b used the old value of a.
  3. 3. A DAG node has only temporary labels and no parent. What can the compiler do with it?

    A node with no live label and no consumers computes a value nobody reads: dead code.
  4. 4. In value numbering, why must the compiler check that the 'holder' variable still has the value number before replacing a statement with x = holder?

    If the holder was overwritten, copying from it would produce a wrong value. The compiler must recompute the expression or use a saved copy.
  5. 5. Which operation does value numbering handle naturally that is awkward in a plain DAG?

    A value number can carry extra facts such as 'this is the constant 0'. Rules like x + 0 = x are then simple lookups.

Summary

  • A DAG represents a basic block with one node per distinct value: leaves are entry values, interior nodes are operations, and labels are the variables currently holding each value.
  • Building it handles common subexpressions, copies and reassignment: a new definition of x moves the label x to a new node.
  • The DAG also reveals dead code (nodes with no live label and no users) and gives valid evaluation orders.
  • Value numbering reaches the same result with a hash table keyed by (operator, value number, value number), sorted for commutative operators, and a check that the holder variable is still valid.
  • Value numbering extends easily to constant folding, copy propagation and algebraic identities, and scales up to superlocal and global numbering on SSA.
  • Pointers, arrays and calls must kill the values that depend on memory.

Next, continue with how information flows across blocks in Dataflow Analysis.