Local Optimization and the DAG

Inside a single basic block there is no branching, no merging — just a straight run of three-address instructions executed top to bottom. That simplicity is an opportunity. If we can capture what the block computes, stripped of the order in which it happened to be written, we can spot every redundant recomputation, every value that is never used, and every copy that could be short-circuited — all at once, with one data structure. That data structure is the directed acyclic graph of the basic block: the DAG.

The catalogue of optimizations gave us common-subexpression elimination, copy propagation and dead-code elimination as separate ideas. The DAG unifies them: build it once, and all three fall out of simply reading it back. This is local optimization at its most elegant — and it is the intellectual seed of global value numbering.

What the DAG is

A DAG for a basic block has one node per distinct computed value:

Leaves are the initial values of variables live on entry — written b_0, c_0, d_0 — and constants.
Interior nodes are labelled with an operator and have edges down to their operand nodes. A node such as + with children b_0 and c_0 represents the value b_0 + c_0.
Each node carries an attached list of variables — every program variable whose current value is that node. When two statements compute the same value, they attach to the same node, and there they are: common subexpressions, detected structurally.

The construction is essentially value numbering: before creating a node for x \; \text{op} \; y, check whether a node with that same operator and those same two operand-nodes already exists. If it does, reuse it; if not, make a new one. The signature \langle \text{op}, \text{left}, \text{right}\rangle is the value's "number", and equal numbers mean equal values.

Building the DAG for a block

Watch the DAG grow for the Dragon Book's classic four-statement block. Each interior node appears as we process its statement; the payoff comes at the last line, where a value we already have is reused rather than recomputed:

a = b + c b = a - d c = b + c d = a - d

The revelation is the fourth statement, d = a - d. Its value is a - d_0 — but that is exactly the value the second statement, b = a - d, already computed. Its node already exists, so we do not build a new one: we just attach the label d to it. The shared node (highlighted) now carries both b and d. That single shared node is the common-subexpression elimination — no separate pass required.

Reading the optimizations off the DAG

Once built, the DAG hands you three optimizations for free when you regenerate code from it:

Optimization	How the DAG delivers it
Common-subexpression elimination	Two computations of the same value map to one node; you emit the operation once.
Dead-code elimination	A node whose attached variables are all dead on exit (and that no live node depends on) need not be evaluated at all — don't emit it.
Copy propagation	A copy `x = y` attaches `x` to `y`'s node instead of making a new one, so later uses read `y` directly.

To regenerate optimised code, walk the interior nodes in an order that respects the edges (children before parents — a topological order), emitting one instruction per live node and, for a node with several attached live variables, one assignment to bind each of them. The block that comes out never computes the same value twice.

The DAG in code

Here is the value-numbering builder. Each interior node is keyed by its signature op,leftId,rightId; if the key is already in the table, we reuse the existing node — that reuse is the detected common subexpression. Watch the log flag the fourth statement.

type Stmt = { dst: string; a: string; op: "+" | "-"; b: string }; interface Node { id: number; label: string; kind: "leaf" | "op"; op?: string; l?: number; r?: number; vars: string[]; } function buildDAG(block: Stmt[]) { const nodes: Node[] = []; const env = new Map<string, number>(); // variable -> current node id const sig = new Map<string, number>(); // "op,l,r" -> node id (value numbering) // Look up a variable's node, creating a leaf (its entry value x0) on first mention. const leafOf = (name: string): number => { if (env.has(name)) return env.get(name)!; const id = nodes.length; nodes.push({ id, label: name + "0", kind: "leaf", vars: [] }); env.set(name, id); return id; }; for (const s of block) { const l = leafOf(s.a); const r = leafOf(s.b); const key = `${s.op},${l},${r}`; let id = sig.get(key); if (id === undefined) { id = nodes.length; nodes.push({ id, label: s.op, kind: "op", op: s.op, l, r, vars: [] }); sig.set(key, id); } else { console.log(` reuse! "${s.dst} = ${s.a} ${s.op} ${s.b}" is a common subexpression of node ${id}`); } // Detach dst from any old node, attach to this one (copy/label bookkeeping). for (const n of nodes) n.vars = n.vars.filter((v) => v !== s.dst); nodes[id].vars.push(s.dst); env.set(s.dst, id); } return nodes; } const block: Stmt[] = [ { dst: "a", a: "b", op: "+", b: "c" }, { dst: "b", a: "a", op: "-", b: "d" }, { dst: "c", a: "b", op: "+", b: "c" }, { dst: "d", a: "a", op: "-", b: "d" }, ]; console.log("building DAG:"); const nodes = buildDAG(block); console.log("\nnodes:"); for (const n of nodes) { const body = n.kind === "leaf" ? n.label : `${n.op}(#${n.l}, #${n.r})`; console.log(` #${n.id} ${body} attached: {${n.vars.join(", ")}}`); }

The output shows node #4 — the value a - d_0 — ending up with both b and d attached, and the fourth statement flagged as a reuse. Four multiplications' worth of source has become three distinct interior nodes.

Because array and pointer stores can invalidate nodes. When you build the DAG and reach an assignment through a memory reference — a[i] = x — you cannot assume any node built from an array load like a[k] is still valid, because i and k might be equal. The safe rule is that a store to a kills every node that loaded from a: they must be recomputed if used again. In the first snippet no intervening store can alias, so y = a[i] reuses the just-stored value; in the second, a[j] = z might alias a[i], so the load node is killed and y = a[i] is recomputed. This conservative killing is exactly what keeps the DAG correct in the presence of aliasing.

A DAG summarises the values computed within one basic block. It knows nothing about what happens across a branch or a loop back-edge, and it treats every variable live on entry as an opaque leaf. So you must never carry a DAG's conclusions across a block boundary: a value that is a "common subexpression" within a block may be recomputed legitimately in a successor block where an operand has changed. Two further traps: a store through a pointer or array kills the loaded-value nodes it might alias (see above), and any function call that could have side effects must be treated as killing whatever it might modify. Global redundancy elimination across blocks needs the heavier machinery of available-expressions dataflow analysis, not a single DAG.