Lesson 13.5 — Local value numbering, memory, DAGs and dead-code elimination¶

Techniques: local value numbering (Cocke–Schwartz) with its extensions — commutativity, algebraic identities, constant folding in the table; value numbering of memory (memory versions, redundant loads, store-to-load forwarding, kills on stores and calls); DAG-based local optimization (Aho–Sethi–Ullman); worklist dead-code elimination · Pebble implements: pebble-lvn (exercise E3) and pebble-dce (exercise E4) · Lab: — (the drill lvn-table is the paper-and-pencil version of E3) · Prerequisites: Lesson 13.1 (scopes), Ch 8 (the value-numbering drill of Lesson 8.3) · Time: 5 hours

Inside one basic block, a compiler can find every expression that recomputes an earlier one by giving each value a number: a + b and b + a get the same number, x + 0 gets the number of x, 2 + 3 gets the number of 5, and a second load p gets the number of the first — unless a store in between may have changed memory. This is local value numbering (LVN), the workhorse of local optimization since Cocke and Schwartz's 1970 notes. The same bookkeeping, drawn as a graph, is the DAG of a basic block that the Dragon book builds to optimize and reassemble blocks. And every replacement leaves dead instructions behind, which dead-code elimination (DCE) sweeps away. This lesson develops all four precisely enough to implement pebble-lvn and pebble-dce and to prove them correct.

1. Problem and motivation¶

Given one basic block, find the instructions whose result equals a value already available earlier in the block, replace their uses by that value, and delete what no longer contributes to the block's effects. Redundancy comes from source code (a[i] + a[i]), from lowering (address computations repeated per access), and from other passes (inlining, unrolling). pebblec runs pebble-lvn and pebble-dce at the end of its Chapter 13 pipeline, after folding, peepholes and reassociation have made equal things look equal.

Local value numbering¶

Cocke and Schwartz described value numbering in their 1970 notes on programming languages and compilers [CS70]: map each expression to a number via a hash table keyed on the operator and its operands' numbers. Cooper and Torczon's presentation adds commutativity, algebraic identities and constant folding in the table [EaC3, Ch. 8]. In SSA form the algorithm simplifies: a name is never reassigned, so no entry is ever invalidated by a later definition.

Memory in value numbering¶

Loads cannot be numbered like arithmetic, because a store between two loads may change the value. The classic solution is to kill every load entry at a store; a cleaner formulation gives memory itself a version that each possibly-writing instruction increments, and puts the version into a load's key. LLVM's EarlyCSE does exactly this with a "generation" counter [LLVM-EarlyCSE]; Chow et al.'s HSSA and LLVM's MemorySSA extend the idea to whole functions (Ch 19).

DAG-based local optimization¶

The Dragon book optimizes a basic block by building its DAG: leaves for initial values, one interior node per distinct computation, and on each node the variables currently holding its value [Dragon2, §8.5]. The DAG exposes common subexpressions (a node with two labels), dead code (a node with no live label), and allows the block to be reassembled in a new order. Instruction selectors use per-block DAGs to this day: LLVM's SelectionDAG performs CSE while building it [LLVM-SelectionDAG].

Dead-code elimination¶

An instruction whose result is unused and that has no side effect can be deleted; doing so may make its operands dead too. The simplest DCE deletes such trivially dead instructions with a worklist (LLVM's dce pass); aggressive DCE instead marks what is needed, starting from side effects, and deletes everything else, which also removes dead cycles (Cytron et al. 1991 in SSA form [CFRWZ91]; EaC's "Dead" [EaC3, Ch. 10]).

2. Definitions and algorithms¶

Definition 13.5.1 (Value number)

A value numbering of a block assigns to every operand \(v\) (argument, constant, instruction result) a number \(\mathrm{VN}(v) \in \mathbb{N}\). Constants with the same type and bits share one number. The holder \(h(n)\) of number \(n\) is the first value that received it and is still in the block (or a constant).

Definition 13.5.2 (Key)

The key of an instruction \(i = \mathsf{op}_F(v_1, \dots, v_k)\) (flags \(F\) are not part of it) is \(\kappa(i) = (\mathsf{op}, \tau, \mathrm{VN}(v_1), \dots, \mathrm{VN}(v_k))\), where \(\tau\) is the result type (for casts), the predicate (for icmp) or the source element type (for getelementptr); for a commutative \(\mathsf{op}\) and for icmp eq/ne the operand numbers are sorted. The denotation of a key is the flag-free operation applied to the values that its numbers stand for.

Algorithm 13.5.3 (Local value numbering with identities and folding)

Input: one basic block \(b\) in SSA form.
Output: \(b\) with every instruction whose value is already available replaced by the earlier value (or constant) and deleted.
Precondition: SSA; operands defined outside \(b\) are leaves.
Postcondition: no two remaining instructions of \(b\) have equal keys; no remaining instruction matches an identity of the table below; no remaining instruction has only constant operands (except division by zero); the result refines \(b\) (Theorem 13.5.12).
Invariant: every value \(x\) that has a number satisfies: whenever \(x\) is not poison, it equals the denotation of the key recorded for \(\mathrm{VN}(x)\) (Lemma 13.5.11).

function LVN(b):
    VN ← empty map;  table ← empty map from keys to numbers;  holder ← []
    mem ← 0                                               # memory version, Algorithm 13.5.5
    for i in instructions(b), in order:
        if i is a load, store or may write memory: MemoryStep(i); continue   # Algorithm 13.5.5
        if i is not an arithmetic/compare/cast/GEP instruction:
            Fresh(i); continue                            # an opaque value
        k ← κ(i)                                          # Definition 13.5.2 (Num of operands)
        if Identity(i) = v: Replace(i, v); continue       # x+0, x*1, x-x, ...
        if every operand number holds a constant c_j and op(c) is not UB:
            Replace(i, the constant op(c)); continue      # folding in the table
        if k ∈ table:
            h ← holder[table[k]]
            flags(h) ← flags(h) ∩ flags(i)                # Theorem 13.5.12
            Replace(i, h); continue
        table[k] ← Fresh(i)

function Num(v):  return VN[v] if v ∈ VN else Fresh(v)   # leaves: arguments, constants, outside values
function Fresh(v): n ← |holder|; holder.append(v); VN[v] ← n; return n
function Replace(i, v): VN[i] ← Num(v); replace every use of i by v; delete i
function Identity(i):                                    # on operand numbers; C(n) = constant held by n
    x + 0, 0 + x, x - 0, x | 0, x ^ 0, x << 0, x >> 0, x * 1, 1 * x  →  x
    x - x, x ^ x, x * 0, 0 * x, x & 0, 0 & x                     →  0
    x & x, x | x                                                →  x
    otherwise none

This is the contract of pebble-lvn (exercise E3) and the oracle of the drill lvn-table (lvn in tools/course/lib/localopt.py).

Memory in value numbering¶

Definition 13.5.4 (Memory version)

Within a block, the memory version \(\mu\) starts at 0 and increases by one at every store and at every instruction that may write memory (a call not marked memory(none) or memory(read), a fence, an atomic or volatile access). The key of a simple (non-volatile, non-atomic) load of type \(\tau\) from pointer \(p\) is \(\kappa(\mathsf{load}) = (\mathsf{load}, \tau, \mathrm{VN}(p), \mu)\).

Algorithm 13.5.5 (Redundant loads and store-to-load forwarding)

Input: one memory instruction \(i\) during Algorithm 13.5.3, with the current table and version \(\mu\).
Output: \(i\) numbered, or replaced by an available value.
Precondition: pointers with equal value numbers are equal addresses (they are equal values, Lemma 13.5.11).
Postcondition: a load is replaced only by a value loaded from, or stored to, the same address with the same type at the same memory version.
Invariant: the table entry \((\mathsf{load}, \tau, n, \mu)\) exists only if the memory at address \(h(n)\), read as \(\tau\), holds the entry's value at every point of version \(\mu\) (Theorem 13.5.13).

function MemoryStep(i):
    if i = store v to p (simple):
        mem ← mem + 1
        table[(load, type(v), Num(p), mem)] ← Num(v)      # forwarding: a load now sees v
    else if i = load τ from p (simple):
        k ← (load, τ, Num(p), mem)
        if k ∈ table: Replace(i, holder[table[k]])
        else: table[k] ← Fresh(i)
    else if i is a call with memory(none) that returns and cannot unwind:
        number it like an operator: key (call, callee, argument numbers)
    else if i may write memory (other calls, volatile/atomic accesses, fences):
        mem ← mem + 1;  Fresh(i) if i has a value

DAG-based local optimization¶

Definition 13.5.6 (DAG of a basic block)

For a block of three-address code \(x \gets y \mathbin{\mathsf{op}} z\) over variables (not SSA), the DAG has a leaf \(v_0\) for the initial value of each variable used before assignment and for each constant, and an interior node for each distinct (operator, children) pair; each node carries a set of labels: the variables whose current value is the node. An assignment \(x \gets \dots\) removes \(x\) from the label set of its previous node. Array stores a[i] = y add a node with an effect and kill every node that reads a (no later computation may reuse them).

Algorithm 13.5.7 (DAG construction)

Input: a block of three-address instructions.
Output: its DAG with labels (Definition 13.5.6).
Precondition: the block has no internal control flow.
Postcondition: each node denotes the value of an expression over the leaves; a variable labels the node of its value at block exit.
Invariant: after instruction \(j\), \(\mathrm{node}(x)\) is the node whose denotation is the value of \(x\) after instruction \(j\), for every variable \(x\) mentioned so far.

function BuildDAG(block):
    node ← empty map from variables to nodes;  memo ← empty map from (op, n1, n2) to nodes
    for "x ← y op z" in block:
        ny ← Leaf(y) if y ∉ node else node[y];  nz ← likewise for z
        key ← (op, ny, nz), children sorted if op is commutative
        if key ∈ memo and memo[key] is not killed: n ← memo[key]
        else: n ← new interior node (op, ny, nz); memo[key] ← n
        if x ∈ node: remove label x from node[x]
        add label x to n;  node[x] ← n
    return the nodes, labels and node map

function Leaf(v): return the unique leaf v₀ (created on first use)

Algorithm 13.5.8 (Reassembly from the DAG)

Input: the DAG of Algorithm 13.5.7 and the set \(\mathit{Out}\) of variables live after the block.
Output: a new block computing the same values of \(\mathit{Out}\).
Precondition: the DAG was built from the block.
Postcondition: for each \(x \in \mathit{Out}\), \(x\) holds the denotation of \(\mathrm{node}(x)\) at exit; nodes not reachable from a label in \(\mathit{Out}\) are not computed.
Invariant: a node is emitted only after its children.

function Reassemble(DAG, Out):
    Needed ← nodes reachable (downwards) from {node[x] | x ∈ Out}
    for n in Needed in topological order (children first), n interior:
        t ← one label of n in Out, if any, else a fresh temporary
        emit "t ← name(child1) op name(child2)";  name(n) ← t
    for x in Out with x ≠ name(node[x]):
        emit "x ← name(node[x])"                          # a copy for a second label

Here \(\mathrm{name}(v_0) = v\) for a leaf; if a leaf's variable is reassigned before an emitted use of \(v_0\), the reassembler saves \(v_0\) in a temporary first (the order constraint of Theorem 13.5.14).

Dead-code elimination¶

Definition 13.5.9 (Trivially dead)

An instruction is trivially dead if it has no uses, is not a terminator or an exception-handling pad, has no side effects (writes no memory, cannot unwind) and is guaranteed to return (willreturn). A division that would be undefined behavior counts as side-effect free (removing UB is a refinement, Lesson 13.8).

Algorithm 13.5.10 (Worklist dead-code elimination)

Input: a function \(f\).
Output: \(f\) without trivially dead instructions.
Precondition: none.
Postcondition: no instruction of the result is trivially dead (Theorem 13.5.15).
Invariant: every trivially dead instruction of the current function is in \(W\).

function DCE(f):
    W ← {i ∈ f | i is trivially dead}
    while W ≠ ∅:
        i ← remove any element of W
        if i is not trivially dead: continue          # it may have been re-added and changed
        for o in operands(i) that are instructions: W ← W ∪ {o}     # may become dead
        delete i
    return f

This is pebble-dce (exercise E4). Aggressive DCE (§6) marks instead of sweeping.

3. Worked example¶

Running example (tests/ch13/lit/lvn-basic.ll @running; inputs \(a, b, c\)):

%t1 = add i32 %a, %b
%t2 = add i32 %b, %a
%t3 = mul i32 %t2, %c
%t4 = mul i32 %c, %t1
%t5 = sub i32 %t4, %t2
%t6 = add i32 %t5, 0
%t7 = mul i32 %t3, 1
%t8 = add i32 %t6, %t7

Local value numbering¶

Algorithm 13.5.3 (the drill oracle's trace; leaves get numbers on first use: \(a{:}0\), \(b{:}1\), \(c{:}3\), \(0{:}6\), \(1{:}7\)):

#	instruction	key	VN	outcome
0	`t1 = add a, b`	(add, 0, 1)	2	new value
1	`t2 = add b, a`	(add, 0, 1) sorted	2	redundant: `t1`
2	`t3 = mul t2, c`	(mul, 2, 3)	4	new value
3	`t4 = mul c, t1`	(mul, 2, 3) sorted	4	redundant: `t3`
4	`t5 = sub t4, t2`	(sub, 4, 2)	5	new value (not commutative)
5	`t6 = add t5, 0`	(add, 5, 6)	5	identity: `t5`
6	`t7 = mul t3, 1`	(mul, 4, 7)	4	identity: `t3`
7	`t8 = add t6, t7`	(add, 4, 5)	8	new value

Four instructions are deleted; the block keeps t1 = add a, b, t3 = mul t1, c, t5 = sub t3, t1, t8 = add t5, t3 (the CHECK lines of lvn-basic.ll).

Memory in value numbering¶

Algorithm 13.5.5 on tests/ch13/lit/lvn-memory.ll @versions (pointers \(p\), \(q\) may alias):

#	instruction	key	\(\mu\) after	VN	outcome
0	`t1 = add a, b`	(add, 0, 1)	0	2	new
1	`t2 = add b, a`	(add, 0, 1)	0	2	redundant: `t1`
2	`l1 = load p`	(load, i32, 3, 0)	0	4	new load
3	`l2 = load p`	(load, i32, 3, 0)	0	4	redundant: `l1`
4	`store t1, q`	records (load, i32, 5, 1) → 2	1	—	forwarding entry
5	`l3 = load p`	(load, i32, 3, 1)	1	6	new: the store may have changed `*p`
6	`l4 = load q`	(load, i32, 5, 1)	1	2	forwarded: `t1`

DAG-based local optimization¶

Algorithm 13.5.7 on the Dragon book's example block (not SSA: b and d are reassigned) [Dragon2, §8.5]:

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

step	instruction	key	node	labels after
1	`a = b + c`	(+, \(b_0\), \(c_0\))	new \(n_1\)	\(n_1\):
2	`b = a - d`	(−, \(n_1\), \(d_0\))	new \(n_2\)	\(n_1\): {a}; \(n_2\):
3	`c = b + c`	(+, \(n_2\), \(c_0\))	new \(n_3\)	\(n_2\): {b}; \(n_3\):
4	`d = a - d`	(−, \(n_1\), \(d_0\))	found \(n_2\)	\(n_2\): {b, d}; \(n_3\):

flowchart BT
  b0([b0]) --> n1["n1: + {a}"]
  c0([c0]) --> n1
  n1 --> n2["n2: − {b, d}"]
  d0([d0]) --> n2
  n2 --> n3["n3: + {c}"]
  c0 --> n3

Reassembly (Algorithm 13.5.8) with all four variables live at exit: a = b + c, d = a - d, c = d + c, b = d — three operations and a copy instead of four operations. If only \(a\) and \(c\) were live, \(n_2\) would get a temporary and there would be no copy. In SSA form (LVN), step 4 is exactly "d redundant with b".

Dead-code elimination¶

Algorithm 13.5.10 on @chain of tests/ch13/lit/dce.ll (the same function as the box in §7); \(W\) is a stack, filled in program order:

step	pop	trivially dead?	effect	\(W\) after
0	—	—	initial: the unused `t3`, `v` (a plain load), `c2` (a pure call), `d` (an unused `sdiv`)	t3 v c2 d
1	`d = sdiv a, 0`	yes	delete	t3 v c2
2	`c2 = call @pure(a)`	yes	delete	t3 v
3	`v = load p`	yes	delete	t3
4	`t3 = shl t2, 2`	yes	delete; push `t2`	t2
5	`t2 = add t1, 1`	yes (its only use is gone)	delete; push `t1`	t1
6	`t1 = mul a, 3`	no (used by `ret`)	—	(empty)

c1 = call @opaque(a) was never in \(W\): the call may write memory.

Try it

./course drill lvn-table --seed 7 --difficulty hard --solution traces extended LVN with loads, stores and calls; ./course drill value-numbering --seed 3 (Ch 8) counts DAG nodes of a non-SSA block with a killed variable.

4. Invariants and correctness¶

Local value numbering¶

Lemma 13.5.11 (Value-number invariant)

At every point of Algorithm 13.5.3, for every value \(x\) with \(\mathrm{VN}(x) = n\): in every execution reaching that point, \(x\) is poison or \(x\) equals the denotation of the key recorded for \(n\) (for a leaf, \(x\) is the holder itself). In particular two values with the same number are equal whenever neither is poison.

Proof

By induction over the steps. Leaves: each gets its own number (constants with equal bits share one, and are equal). Fresh(i) for a new key: \(i\) computes \(\mathsf{op}_F\) of its operands; by the induction hypothesis each operand equals the denotation of its number when not poison, so \(i\) equals the flag-free operation on those denotations — the key's denotation — unless \(i\) is poison (an operand is poison, or a flag fails). Opaque values (loads, calls) are leaves. Replace(i, v) gives \(i\) the number of \(v\); by the correctness of the identity, the fold or the table hit (Theorem 13.5.12), \(i\) equals \(v\) where \(i\) is not poison. SSA guarantees that no value changes after it is numbered, so the property, once true, stays true.

Theorem 13.5.12 (Local value numbering is a refinement)

Every replacement made by Algorithm 13.5.3 turns the block into one that refines it, provided the holder's flags are intersected with the replaced instruction's. Without the intersection, replacing a flag-free instruction by an earlier one with nsw is not a refinement.

Proof

Table hit. \(i\) and the holder \(h\) have the same key, so the same operation on operands with the same numbers, which by Lemma 13.5.11 are equal values (or poison, which then makes both \(i\) and \(h\) poison through rule P-Op of Definition 9.7.4). They can differ only in flags. After \(\mathit{flags}(h) \gets \mathit{flags}(h) \cap \mathit{flags}(i)\): (a) \(h\)'s new version refines its old version (fewer flags only remove poison, Definition 9.7.3), so its earlier uses are fine; (b) whenever \(i\) is not poison, every flag of \(i\) holds, hence every flag of the intersection, so \(h\) is not poison and equals \(i\) — i.e. \(h\) refines \(i\) at every use of \(i\). By Theorem 9.7.16 the replacement is a refinement of the whole block. Counterexample without intersection: \(h\) = add nsw i8 %x, %y, \(i\) = add i8 %x, %y, \(x = y = 100\): \(i = -56\), \(h = \mathsf{poison}\); replacing \(i\) by \(h\) makes a defined value poison (tests/ch13/lit/lvn-flags.ll). Identities. \(x + 0\), \(x - 0\), \(x \mid 0\), \(x \oplus 0\), \(x \ll 0\), \(x \gg 0\) and \(x \cdot 1\) equal \(x\) exactly and their flags cannot fail (no overflow is possible, no bit is shifted out); \(x - x\), \(x \oplus x\), \(x \cdot 0\), \(x \mathbin{\&} 0\) are \(0\) unless \(x\) is poison, in which case the source is poison and \(0\) refines it; \(x \mathbin{\&} x = x \mid x = x\). Folding. Theorem 13.1.12. In each case the replacement refines \(i\), and Theorem 9.7.16 lifts it to the block.

Memory in value numbering¶

Theorem 13.5.13 (Memory versions are sound)

If a simple load \(i\) of type \(\tau\) from \(p\) is replaced by the value \(v\) recorded under key \((\mathsf{load}, \tau, \mathrm{VN}(p), \mu)\), then in every execution \(i\) would have loaded a value refined by \(v\).

Proof

The entry was created at some instruction \(j\) before \(i\) in the block with the same memory version \(\mu\) — either a load of \(\tau\) from \(p'\) with \(\mathrm{VN}(p') = \mathrm{VN}(p)\) (then \(v = j\)), or a store of \(v\) of type \(\tau\) to such a \(p'\) (then \(\mu\) was just incremented by it). By Lemma 13.5.11 \(p' = p\) as addresses (pointers are never poison at a non-UB load; if \(p\) is poison the load \(i\) is UB and anything refines it). Since the version did not change between \(j\) and \(i\), no instruction between them may write memory (Definition 13.5.4): the bytes at \(p\) are the same at \(i\) as right after \(j\). A second load of the same type from unchanged bytes returns the same value; a load of type \(\tau\) right after a store of a value of type \(\tau\) to the same address returns that value (LangRef, "load" and "store": the stored bytes are read back as the stored value, poison included). Volatile and atomic accesses are excluded, as the LangRef allows them to observe other agents.

When it breaks. Keys without the type would forward an i32 store to an i8 load (a different value: the low byte on little-endian targets). Not bumping the version at a call that may write memory makes the replacement wrong whenever the callee stores to p. And the version bump is conservative: a store to q kills load p even when p and q never alias; alias analysis (Ch 19) removes such false kills.

DAG-based local optimization¶

Theorem 13.5.14 (DAG construction and reassembly preserve the block's outputs)

For the DAG of Algorithm 13.5.7, the invariant holds after every instruction; and the block produced by Algorithm 13.5.8 leaves every \(x \in \mathit{Out}\) with the value the original block leaves in it, provided each leaf's initial value is still available (saved in a temporary if its variable is overwritten before its last emitted use).

Proof

Invariant. Initially no variable has a node. For x ← y op z, the node found or created has denotation \(\mathsf{op}\) applied to the denotations of \(\mathrm{node}(y)\) and \(\mathrm{node}(z)\) (or the leaves), which by the invariant are the current values of \(y\) and \(z\): so it denotes the new value of \(x\). A found node \(n = \mathrm{memo}[\mathit{key}]\) denotes the same expression over the leaves, and leaves are initial values that never change: equal expressions have equal values. Only \(x\)'s node changes. (Array stores kill memo entries that read the array, so a stale node is never found.) Reassembly. Nodes are emitted children-first, each exactly once, and each emitted instruction computes its node's denotation from its children's names; a copy gives every live label its node's value. Leaves are named by their variables, which is correct as long as the variable still holds its initial value — the stated proviso. Nodes not needed by \(\mathit{Out}\) are not emitted, which removes only computations without side effects. Full treatment: [Dragon2, §8.5].

Dead-code elimination¶

Theorem 13.5.15 (Worklist DCE is a refinement and reaches a fixed point)

Deleting a trivially dead instruction is a refinement. Algorithm 13.5.10 terminates after at most \(n + \sum_i \lvert \mathrm{operands}(i) \rvert\) iterations, and its result has no trivially dead instruction.

Proof

Refinement: a trivially dead instruction has no uses, so no value of the program depends on it; it writes no memory and cannot unwind, so no observable effect depends on it; it always returns, so it cannot be the reason an execution does not terminate. Its only remaining behavior is possible immediate UB (division by zero), and removing UB is a refinement (Definition 9.7.8: a UB execution allows every behavior). Termination: each iteration removes one element of \(W\); elements enter initially (\(\le n\)) and once per (deleted instruction, operand) pair. Fixed point: deleting \(i\) changes only the use counts of \(i\)'s operands, so only they can become trivially dead, and they are added; the invariant holds, and \(W = \emptyset\) at the end.

When it breaks. A cycle of instructions that only use each other (a phi and its increment, @loop in dce.ll) is never trivially dead: each has a use. Only a marking algorithm (aggressive DCE, §6) removes it; the box in §7 shows LLVM's dce keeping and adce removing such a cycle.

5. Complexity¶

Technique	Time (worst)	Time (typical)	Space	Variables
Local value numbering	\(O(n)\) expected; \(O(n^2)\) if every key collides	linear	\(O(n)\) table	\(n\) instructions in the block
Memory in value numbering	\(O(1)\) extra per memory instruction	linear	\(O(n)\)	—
DAG construction + reassembly	\(O(n)\) expected (hashing) + \(O(n)\) topological order	linear	\(O(n)\) nodes	\(n\) instructions
Register-optimal reassembly of a DAG	NP-complete [AJU77]	heuristics	—	—
Worklist DCE	\(O(n + u)\)	linear	\(O(n)\)	\(u\) = total operand count
Aggressive (mark-sweep) DCE	\(O(n + u + e)\)	linear	\(O(n)\)	\(e\) CFG edges (control dependence)

Justification. LVN does one hash lookup and at most one insertion per instruction, each expected \(O(1)\) with a good hash; keys have bounded size (two or three operands). A memory instruction adds a counter update. The DAG is LVN plus labels; reassembly visits each needed node once. DCE: Theorem 13.5.15.

Pathological families. (1) Kills defeat memory numbering: a block \(\ell_1 = \mathsf{load}\ p\), \(\mathsf{store}\ \dots, q\), \(\ell_2 = \mathsf{load}\ p\), \(\mathsf{store}\ \dots, q\), … with \(n\) loads of \(p\) finds no redundancy at all, because each store bumps the version — although with \(p \ne q\) all loads are equal; alias analysis is the cure. (2) Keys that collide: \(n\) distinct expressions whose keys hash to one bucket turn each lookup into a scan: \(\Theta(n^2)\). (3) DCE order: a chain of \(n\) dead instructions each used only by the next is removed in \(n\) iterations by the worklist, but a sweep that visits instructions top-down deletes only the last one per sweep: \(\Theta(n^2)\) over \(n\) sweeps.

Local value numbering¶

Superlocal and dominator-based VN (Lesson 13.1, Algorithm 13.1.4; [BCS97]): the same table, scoped. Trade-off: needs EBBs or the dominator tree.
Global value numbering: hash-based over SSA with phis (GVN, NewGVN) or partition-based (Alpern–Wegman–Zadeck) — Ch 17. Trade-off: iteration to a fixed point.
Non-SSA LVN needs to kill keys that mention a reassigned variable (the Ch 8 drill value-numbering). Trade-off: more bookkeeping; SSA removes it.

Memory in value numbering¶

Alias-aware kills: a store only bumps the versions of locations it may alias (GVN with MemoryDependence, EarlyCSE with MemorySSA: early-cse<memssa>). Trade-off: alias-analysis cost.
Dead-store elimination is the dual: a store overwritten before any load is dead (EarlyCSE's LastStore logic) [LLVM-EarlyCSE].
Heap SSA / MemorySSA give memory a global SSA form (Ch 19).

DAG-based local optimization¶

SelectionDAG: one DAG per block, built with CSE (CSEMap), combined (DAGCombiner), legalized and selected [LLVM-SelectionDAG]. Trade-off: block-local; GlobalISel works on the whole function (Ch 21).
Sea of nodes: a single global graph of values and control (HotSpot C2, V8's former TurboFan) (Ch 8). Trade-off: scheduling becomes a separate problem.
Algebraic identities and array kills in the DAG [Dragon2, §8.5].

Dead-code elimination¶

Aggressive DCE (mark live from side effects, sweep the rest, including dead control flow) [CFRWZ91]; LLVM adce. Trade-off: needs control dependence.
Bit-tracking DCE removes computations whose bits are not demanded (LLVM bdce, DemandedBits). Trade-off: bit-level analysis.
DCE inside other passes: InstCombine, EarlyCSE and every worklist engine delete trivially dead instructions as they go (EraseDead in Algorithm 13.2.4).

7. In real compilers¶

Local value numbering¶

GCC's value numbering (FRE) on a commuted redundancy

Reproduce (gcc 13.3.0; Linux):

cat > fre.c <<'EOF'
int f(int a, int b, int c) {
  int t1 = a + b;
  int t2 = b + a;
  int t3 = t2 * c;
  int t4 = c * t1;
  return t3 - t4 + (t1 - t2);
}
EOF
gcc -O1 -c fre.c -fdump-tree-fre1-details=fre.txt -o /dev/null
grep 'Value numbering stmt\|Replaced\|Removing dead' fre.txt
sed -n '/<bb 2>/,/^}/p' fre.txt

Output (complete):

Value numbering stmt = t1_5 = a_3(D) + b_4(D);
Value numbering stmt = t2_6 = a_3(D) + b_4(D);
Replaced a_3(D) + b_4(D) with t1_5 in all uses of t2_6 = a_3(D) + b_4(D);
Value numbering stmt = t3_8 = t2_6 * c_7(D);
Value numbering stmt = t4_9 = t1_5 * c_7(D);
Replaced t1_5 * c_7(D) with t3_8 in all uses of t4_9 = t1_5 * c_7(D);
Value numbering stmt = _1 = t3_8 - t4_9;
Replaced t3_8 - t4_9 with 0 in all uses of _1 = t3_8 - t4_9;
Value numbering stmt = return _1;
Removing dead stmt _1 = t3_8 - t4_9;
Removing dead stmt t4_9 = t1_5 * c_7(D);
Removing dead stmt t2_6 = a_3(D) + b_4(D);
  <bb 2> :
  t1_5 = a_3(D) + b_4(D);
  t3_8 = t1_5 * c_7(D);
  return 0;

}

What to notice: GCC canonicalizes b + a to a + b (Lesson 13.4), so its value numbering finds t2 redundant with t1, then t1 * c with t3, then folds t3 - t4 to 0 in the table (the identity \(x - x\)), and finally removes the dead statements: exactly the steps of Algorithm 13.5.3, in GCC's SCCVN (gcc/tree-ssa-sccvn.cc at releases/gcc-15.1.0) [GCC-sccvn].

Memory in value numbering¶

EarlyCSE's memory generations

Reproduce (opt 23.1.2; LLVM 23.1.2 sources via curl):

cat > lvn.ll <<'EOF'
define i32 @lvn(i32 %a, i32 %b, ptr %p, ptr %q) {
  %t1 = add i32 %a, %b
  %t2 = add i32 %b, %a          ; commuted: same value as %t1
  %l1 = load i32, ptr %p
  %l2 = load i32, ptr %p        ; redundant load
  store i32 %t1, ptr %q         ; may alias %p: new memory version
  %l3 = load i32, ptr %p        ; NOT redundant
  %l4 = load i32, ptr %q        ; forwarded from the store
  %s1 = add i32 %t2, %l2
  %s2 = add i32 %s1, %l3
  %s3 = add i32 %s2, %l4
  %s4 = add i32 %s3, %l1
  ret i32 %s4
}
EOF
opt -passes=early-cse -S lvn.ll | sed -n '/^define/,/^}/p'
curl -sL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/lib/Transforms/Scalar/EarlyCSE.cpp \
  | grep -B2 -A2 'unsigned CurrentGeneration = 0;'

Output (complete):

define i32 @lvn(i32 %a, i32 %b, ptr %p, ptr %q) {
  %t1 = add i32 %a, %b
  %l1 = load i32, ptr %p, align 4
  store i32 %t1, ptr %q, align 4
  %l3 = load i32, ptr %p, align 4
  %s1 = add i32 %t1, %l1
  %s2 = add i32 %s1, %l3
  %s3 = add i32 %s2, %t1
  %s4 = add i32 %s3, %l1
  ret i32 %s4
}

  /// This is the current generation of the memory value.
  unsigned CurrentGeneration = 0;

  /// Set up the EarlyCSE runner for a particular function.

What to notice: %t2 is replaced by %t1 (commutativity), %l2 by %l1 (same address, same generation), %l4 by the stored %t1 (forwarding), and %l3 stays because the store to %q bumped the generation — EarlyCSE's CurrentGeneration is the memory version of Definition 13.5.4 (llvm/lib/Transforms/Scalar/EarlyCSE.cpp, EarlyCSE::processNode) [LLVM-EarlyCSE].

DAG-based local optimization¶

SelectionDAG builds a CSE'd DAG per block

Reproduce (llc 23.1.2; LLVM 23.1.2 sources via curl):

cat > dag.ll <<'EOF'
define i32 @dag(i32 %a, i32 %b) {
  %t1 = add i32 %a, %b
  %t2 = add i32 %a, %b
  %t3 = mul i32 %t1, %t2
  ret i32 %t3
}
EOF
llc -O2 -mtriple=x86_64-linux-gnu -stop-after=finalize-isel dag.ll -o - | sed -n '/^  bb.0/,/RET/p'
curl -sL https://raw.githubusercontent.com/llvm/llvm-project/llvmorg-23.1.2/llvm/include/llvm/CodeGen/SelectionDAG.h \
  | grep -B2 'FoldingSet<SDNode> CSEMap;'

Output (complete):

  bb.0 (%ir-block.0):
    liveins: $edi, $esi

    %1:gr32 = COPY $esi
    %0:gr32 = COPY $edi
    %2:gr32 = ADD32rr %0, %1, implicit-def dead $eflags
    %3:gr32 = IMUL32rr %2, %2, implicit-def dead $eflags
    $eax = COPY %3
    RET 0, $eax
  /// This structure is used to memoize nodes, automatically performing
  /// CSE with existing nodes when a duplicate is requested.
  FoldingSet<SDNode> CSEMap;

What to notice: the IR computes add %a, %b twice, and no IR pass ran; after instruction selection there is a single ADD32rr feeding both operands of IMUL32rr, because building the block's SelectionDAG went through SelectionDAG::getNode, which looks every node up in CSEMap first (llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp) [LLVM-SelectionDAG].

Dead-code elimination¶

LLVM's dce and adce

Reproduce (opt 23.1.2; any OS):

cat > dce.ll <<'EOF'
declare i32 @opaque(i32)
declare i32 @pure(i32) memory(none) nounwind willreturn
define i32 @chain(i32 %a, ptr %p) {
  %t1 = mul i32 %a, 3
  %t2 = add i32 %t1, 1
  %t3 = shl i32 %t2, 2
  %v  = load i32, ptr %p
  %c1 = call i32 @opaque(i32 %a)
  %c2 = call i32 @pure(i32 %a)
  %d  = sdiv i32 %a, 0
  ret i32 %t1
}
define i32 @cycle(i32 %n) {
entry:
  br label %loop
loop:
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
  %acc.next = add i32 %acc, 3
  %i.next = add i32 %i, 1
  %c = icmp slt i32 %i.next, %n
  br i1 %c, label %loop, label %exit
exit:
  ret i32 %i.next
}
EOF
for p in dce adce; do
  echo "=== $p"; opt -passes=$p -S dce.ll | sed -n '/^define i32 @chain/,/^}/p;/^loop:/,/br i1/p'
done

Output (complete):

=== dce
define i32 @chain(i32 %a, ptr %p) {
  %t1 = mul i32 %a, 3
  %c1 = call i32 @opaque(i32 %a)
  ret i32 %t1
}
loop:                                             ; preds = %loop, %entry
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %acc = phi i32 [ 0, %entry ], [ %acc.next, %loop ]
  %acc.next = add i32 %acc, 3
  %i.next = add i32 %i, 1
  %c = icmp slt i32 %i.next, %n
  br i1 %c, label %loop, label %exit
=== adce
define i32 @chain(i32 %a, ptr %p) {
  %t1 = mul i32 %a, 3
  %c1 = call i32 @opaque(i32 %a)
  ret i32 %t1
}
loop:                                             ; preds = %loop, %entry
  %i = phi i32 [ 0, %entry ], [ %i.next, %loop ]
  %i.next = add i32 %i, 1
  %c = icmp slt i32 %i.next, %n
  br i1 %c, label %loop, label %exit

What to notice: both passes remove the chain t3, t2, the unused load, the pure call and the unused sdiv of @chain, and keep the call to @opaque. Only adce removes the self-sustaining cycle %acc/%acc.next of @cycle: worklist DCE (llvm/lib/Transforms/Scalar/DCE.cpp, eliminateDeadCode with isInstructionTriviallyDead) never sees it as dead (§4, "When it breaks"), while aggressive DCE (ADCE.cpp) marks from side effects [LLVM-DCE].

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Local value numbering	All redundancy within a block, up to commutativity and the identities it knows	\(O(n)\) expected · very fast	Needs flag intersection to be sound	Low (a hash table)	EarlyCSE/GVN building block, `pebble-lvn`
Memory in value numbering	Redundant loads and forwarding between writes; conservative at every store/call	\(O(1)\) per memory op	Sound without alias analysis, imprecise	Low (a counter)	EarlyCSE generations, GVN with MemDep, MemorySSA
DAG-based local optimization	Same redundancy as LVN, plus reordering and dead-node removal for non-SSA code	\(O(n)\) · fast	Reassembly choices affect registers (NP-hard to optimize)	Medium	Textbook block optimization, SelectionDAG
Worklist DCE	Removes trivially dead code, not dead cycles	\(O(n + u)\) · very fast	Always sound	Lowest	Every pass cleans up after itself; `dce`, `pebble-dce`

Choose LVN on SSA code as the first redundancy eliminator (then widen its scope, Lesson 13.1). Choose memory versions whenever loads repeat; add alias analysis when stores to unrelated pointers kill too much. Choose a DAG when you also want to reorder or reassemble a block, as instruction selectors do, or when the code is not in SSA form. Choose worklist DCE after every transformation; use aggressive DCE once per pipeline to remove dead cycles and branches.

9. Assessment¶

Technique	Quiz questions	Drills	Flashcards	Exercises
Local value numbering	`lvn-trace`, `lvn-flags`	`./course drill lvn-table`	tag `lvn`	E3 (`pebble-lvn`)
Memory in value numbering	`lvn-memory`, `find-earlycse-generation`	`./course drill lvn-table --difficulty medium`	tag `memory-vn`	E3
DAG-based local optimization	`dag-nodes`, `find-csemap`	`./course drill value-numbering` (Ch 8: DAG node counts)	tag `dag`	—
Dead-code elimination	`dce-order`, `dce-cycle`	justification: DCE is a single rule ("no uses, no effects"); it is exercised by E4's tests and the quiz traces rather than a generated drill	tag `dce`	E4 (`pebble-dce`)

References¶

See the chapter references.

Lesson 13.5 — Local value numbering, memory, DAGs and dead-code elimination¶

1. Problem and motivation¶

Local value numbering¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

2. Definitions and algorithms¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

3. Worked example¶

Local value numbering¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

4. Invariants and correctness¶

Local value numbering¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

5. Complexity¶

6. Variants and refinements¶

Local value numbering¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

7. In real compilers¶

Local value numbering¶

Memory in value numbering¶

DAG-based local optimization¶

Dead-code elimination¶

8. Comparison¶

9. Assessment¶

References¶