Lesson 17.3 — Dead code elimination: mark–sweep, aggressive (control dependence), and dead stores¶

Techniques: mark–sweep "useful code" DCE (Kennedy 1981; Cooper–Torczon's Dead); aggressive DCE via control dependence (Cytron et al. 1991), including LLVM's handling of loops that may not terminate; dead-store elimination and its interplay with branch elimination · Pebble implements: pebble-adce (exercise E2) · Prerequisites: worklist DCE of trivially dead instructions (Ch 13, Lesson 13.5); post-dominance and control dependence (Lesson 15.4) · Time: 4–6 hours

1. Problem and motivation¶

An instruction is dead if deleting it cannot change what the program does: its result is never used by anything observable, and it has no side effect. Ch 13's worklist DCE deletes trivially dead instructions — those with no uses — and repeats. It is sound and fast, but it cannot delete a cycle of dead values, and it never deletes a branch. The running example of this lesson (the work function of the §7 boxes, in the chapter's compact notation with LLVM's latch block for.inc merged into for.body) has both:

fn work(n, a):
entry:
  br for.cond
for.cond:
  s.0 = phi [0, entry], [add, for.body]
  t.0 = phi [0, entry], [add1, for.body]
  i.0 = phi [0, entry], [inc, for.body]
  cmp = lt i.0, n
  cbr cmp, for.body, for.end
for.body:
  add = add s.0, i.0
  mul = mul a, i.0
  add1 = add t.0, mul
  inc = add i.0, 1
  br for.cond
for.end:
  cmp2 = lt 5, a
  cbr cmp2, if.then, if.end
if.then:
  mul3 = mul t.0, 2
  br if.end
if.end:
  ret s.0

flowchart TD
  entry([entry]) --> fc[for.cond]
  fc -->|T| fb[for.body]
  fc -->|F| fe[for.end]
  fb --> fc
  fe -->|T| it[if.then]
  fe -->|F| ie[if.end]
  it --> ie

t.0 and add1 use each other, so neither is trivially dead, although nothing observable depends on them; and the test a > 5 decides nothing that matters once mul3 is gone.

Mark–sweep DCE¶

The fix for cycles is to reverse the question: instead of proving instructions dead, prove them useful starting from the instructions that are obviously needed (returns, stores, calls with effects, branches) and following operands backwards; whatever is never reached is dead [EaC3, Ch. 10]. This "mark–sweep" formulation goes back to Kennedy's survey of global flow analysis and is the Dead algorithm of Engineering a Compiler. It removes t.0, add1, mul and mul3 from the running example but keeps every branch.

Aggressive DCE¶

Cytron, Ferrante, Rosen, Wegman and Zadeck made branches optional too: a branch is useful only if some useful instruction is control dependent on it [CFRWZ91, §7.1]. Everything starts dead, including branches; marking a useful instruction also marks the branches that decide whether it executes. A branch that remains unmarked is replaced by a jump to its nearest useful post-dominator. On the running example ADCE also removes cmp2 and the branch in for.end, and on a loop whose results are unused it removes the whole loop — which is only correct if the loop terminates. LLVM's adce [LLVM-ADCE] and GCC's cddce [GCC-DCE] both implement it and both answer the termination question explicitly; pebble-adce (E2) does the same.

Dead stores and dead branches¶

A store is an effect, so both algorithms treat it as a root. But a store whose value is overwritten before any read, or written to a local variable nobody reads, is dead as well; finding it needs memory reasoning (MemorySSA, alias analysis: Ch 19). Dead-store elimination (DSE) removes such stores [LLVM-DSE], and it interacts with ADCE: removing a dead store can make the branch around it dead, and only then can ADCE remove the branch.

2. Definitions and algorithms¶

Definition 17.3.1 (Roots, observable behavior, useful instructions)

The observable behavior of a run of \(F\) is the sequence of its side effects (stores, calls, volatile accesses, I/O) with their operand values, and its returned value or non-termination. An instruction is a root if it can contribute to observable behavior directly: ret, stores, calls that may write memory or may not return, volatile accesses, EH pads. For a set of root branches \(R_b\), the useful instructions are the least set \(\mathcal{U}\) that contains the roots and \(R_b\), and contains the definition of every operand of a member of \(\mathcal{U}\). Everything else is dead relative to \(R_b\).

Useful instructions of work

With every branch a root (\(R_b\) = all branches): \(\mathcal{U}\) = the branches, cmp, cmp2, ret s.0, s.0, add, i.0, inc. Dead: t.0, add1, mul, mul3.

Algorithm 17.3.2 (Mark–sweep DCE)

Input: an SSA function.
Output: the function without the instructions that are not useful when every branch is a root.
Precondition: side effects are known per instruction (Definition 17.3.1).
Postcondition: exactly \(\mathcal{U}\) (with \(R_b\) = all terminators) survives; the CFG is unchanged (Theorem 17.3.9).
Invariant: every marked instruction is useful; every marked instruction whose operands are not yet all marked is on the worklist.

function MarkSweepDCE(F):
    Marked ← ∅;  W ← []
    for each instruction I:
        if I is a root or a terminator: Marked ← Marked ∪ {I}; push I on W
    while W ≠ []:
        I ← pop W
        for each operand v of I that is an instruction:
            if v ∉ Marked: Marked ← Marked ∪ {v}; push v on W
    for each instruction I ∉ Marked: delete I

Definition 17.3.3 (Control dependence, recalled)

Let every block reach an exit, and let \(\mathrm{pdom}\) be post-dominance on the CFG with a virtual exit (Lesson 15.4). Block \(Y\) is control dependent on block \(X\), \(X \in \mathrm{CD}(Y)\), if \(X\) has a successor \(S\) with \(Y \mathrel{\mathrm{pdom}} S\) and \(Y\) does not strictly post-dominate \(X\). Equivalently \(\mathrm{CD}(Y)\) is the post-dominance frontier of \(Y\) (Ch 15, Theorem 15.4.6).

Definition 17.3.4 (ADCE marking)

The ADCE live set \(\mathcal{L}\) and useful blocks \(\mathcal{B}\) are the least sets such that: (1) every root is in \(\mathcal{L}\) (branches are not roots, except the ones of rule (6)); (2) the entry block is in \(\mathcal{B}\); (3) if \(I \in \mathcal{L}\) then \(\mathrm{block}(I) \in \mathcal{B}\) and the definitions of \(I\)'s operands are in \(\mathcal{L}\); (4) if a phi in \(\mathcal{L}\) has incoming block \(P\), then \(P \in \mathcal{B}\); (5) if \(B \in \mathcal{B}\) then its unconditional branch (if any) and the terminator of every \(X \in \mathrm{CD}(B)\) are in \(\mathcal{L}\); (6) optionally, the terminators of blocks that end a retreating edge of a depth-first search from the entry (an edge to a block still on the DFS stack) are in \(\mathcal{L}\) (loops that may not terminate are kept; §4). On a reducible CFG the retreating edges are exactly the back edges \(T \to H\) with \(H \mathrel{\mathrm{dom}} T\); on an irreducible one a cycle may have no such back edge, but every cycle contains a retreating edge.

Algorithm 17.3.5 (Aggressive dead code elimination, Cytron et al.)

Input: an SSA function in which every block reaches a ret (or, with rule (6), any function); its post-dominator tree and control dependences.
Output: the function without dead instructions; dead conditional branches replaced by jumps.
Precondition: the conditions of Definition 17.3.3; if rule (6) is off, every loop terminates.
Postcondition: \(\mathcal{L}\) and \(\mathcal{B}\) of Definition 17.3.4 are computed; the result has the same observable behavior (Theorem 17.3.11).
Invariant: every marked instruction is in \(\mathcal{L}\) and every marked block in \(\mathcal{B}\); every marked instruction whose consequences (3)–(5) are not yet applied is on the worklist.

function ADCE(F):
    Live ← ∅; Useful ← ∅; W ← []
    for each root I: Mark(I)
    if keep loops: for each DFS retreating edge (T → H): Mark(terminator(T))
    MarkBlock(entry)
    while W ≠ []:
        I ← pop W
        for each operand v of I that is an instruction: Mark(v)
        if I is a phi: for each incoming block P: MarkBlock(P)
    for each block X whose conditional branch is not in Live:          # sweep
        Y ← ipdom(X)
        while Y ∉ Useful: Y ← ipdom(Y)                                  # nearest useful post-dominator
        replace the terminator of X by `br Y`   (add a poison phi entry in Y if X→Y is a new edge)
    delete every instruction not in Live (except terminators of kept blocks)
    delete the blocks that became unreachable
function Mark(I):
    if I ∉ Live: Live ← Live ∪ {I}; push I on W; MarkBlock(block(I))
function MarkBlock(B):
    if B ∉ Useful:
        Useful ← Useful ∪ {B}
        if B ends in `br S`: Mark(terminator(B))
        for each X in CD(B): Mark(terminator(X))

scalaropt.adce in tools/course/lib is this pseudo-code (with aggressive=False it becomes Algorithm 17.3.2, with remove_loops=False rule (6) is on); the drill adce-marking traces it.

Definition 17.3.6 (Dead store)

A store \(s\) to location \(\ell\) is dead if on every path from \(s\) to an exit, \(\ell\) is overwritten (by a store that writes all of \(\ell\)'s bytes) before any instruction that may read \(\ell\), or no read of \(\ell\) can happen at all before the location's lifetime ends (a non-escaping alloca at ret).

Algorithm 17.3.7 (Dead-store elimination, two classic cases)

Input: an SSA function with loads and stores, and an alias oracle \(\mathrm{mayAlias}\), \(\mathrm{mustOverwrite}\).
Output: the function without the stores the two rules below prove dead.
Precondition: the alias oracle is sound (a "no" answer is never wrong).
Postcondition: every deleted store is dead (Definition 17.3.6; Theorem 17.3.12).
Invariant: while scanning a block backwards, Covered holds the locations surely overwritten before any possible read later in the block.

function DSE(F):
    for each block B:                                  # rule 1: overwritten later in the block
        Covered ← ∅
        for each instruction I of B, last to first:
            if I is `store v, ℓ`:
                if some c ∈ Covered with mustOverwrite(c, ℓ): delete I
                else: Covered ← Covered ∪ {ℓ}
            else if I may read memory ℓ' (load, call):
                Covered ← { c ∈ Covered : not mayAlias(c, ℓ') }
    for each alloca A whose address never escapes:    # rule 2: never read at all
        if no load or call can read A: delete every store to A (and A)

LLVM's DSE generalizes rule 1 across blocks by walking MemorySSA from each store to its possible readers and killers (Ch 19).

3. Worked example¶

Mark–sweep DCE¶

Algorithm 17.3.2 on work (scalaropt.adce(fn, aggressive=False)); the seeds are the six terminators, then the worklist proceeds in FIFO order:

step	action	because	worklist after
1–6	mark `entry.term`, `for.cond.term`, `for.body.term`, `for.end.term`, `if.then.term`, `if.end.term`	roots: every branch, and the return	the six terminators
7	pop `entry.term`	no operands	5 terminators
8	pop `for.cond.term`; mark `cmp`	operand of the branch	… `cmp`
9	pop `for.body.term`, `for.end.term`; mark `cmp2`	operand of the branch	`if.then.term if.end.term cmp cmp2`
10	pop `if.then.term`, `if.end.term`; mark `s.0`	operand of `ret`	`cmp cmp2 s.0`
11	pop `cmp`; mark `i.0`	operand	`cmp2 s.0 i.0`
12	pop `cmp2` (operands `5`, `a`: nothing to mark), `s.0`; mark `add`	phi operand	`i.0 add`
13	pop `i.0`; mark `inc`	phi operand	`add inc`
14	pop `add`, `inc`	operands already marked	—

Dead: t.0, mul, add1, mul3. The dead cycle t.0 ↔ add1 is found because nobody marks it; Ch 13's trivially-dead worklist cannot delete either (each has a use). for.end still tests a > 5 and branches to an empty if.then.

Aggressive DCE¶

Algorithm 17.3.5 on work, generated by scalaropt.adce(fn) (control dependences: \(\mathrm{CD}(\text{for.cond}) = \mathrm{CD}(\text{for.body}) = \{\text{for.cond}\}\), \(\mathrm{CD}(\text{if.then}) = \{\text{for.end}\}\), all others empty):

step	action	because	worklist after
1	mark `if.end.term`	root: return	if.end.term
2	block `entry` useful	the entry block is always useful	if.end.term
3	mark `entry.term`	unconditional branch of useful block `entry`	if.end.term entry.term
4	block `if.end` useful	contains live `if.end.term`	entry.term
5	mark `s.0`	operand of `if.end.term`	entry.term s.0
6	block `for.cond` useful	contains live `s.0`	—
7	mark `for.cond.term`	`for.cond` is control dependent on `for.cond`	for.cond.term
8	mark `add`	operand of `s.0`	for.cond.term add
9	block `for.body` useful	incoming block of live phi `s.0`	for.cond.term add
10	mark `for.body.term`	unconditional branch of useful block `for.body`	for.cond.term add for.body.term
11	mark `cmp`	operand of `for.cond.term`	add for.body.term cmp
12	mark `i.0`	operand of `add`	for.body.term cmp i.0
13	mark `inc`	operand of `i.0`	inc

(Rows 5 and 6 each come from popping one instruction; the table shows every change of the live sets.) Useful blocks: entry, for.cond, for.body, if.end. for.end is not useful: nothing live is in it and no useful block is control dependent on it. Its dead branch is rewritten to its nearest useful post-dominator, \(\mathrm{ipdom}(\text{for.end}) = \text{if.end}\); if.then becomes unreachable and is deleted:

for.end:
  br if.end
if.end:
  ret s.0

Dead: t.0, mul, add1, cmp2, for.end.term (rewritten), mul3, if.then.term. The loop survives because s.0 is live and for.cond is control dependent on itself. Loops: if work returned a instead of s.0, nothing in the loop would be live, and ADCE would rewrite for.cond's branch to if.end — deleting the whole loop (scalaropt.adce reports 14 dead instructions); with remove_loops=False (rule (6)), for.body's back-edge branch is a root and the loop control (i.0, inc, cmp) stays.

Try it

./course drill adce-marking --seed 2 --difficulty hard --solution: dead instructions, branch retargets, and what ADCE removes beyond mark–sweep DCE.

Dead stores and dead branches¶

In @inter of the §7 box, block a computes %y and stores it into a local alloca that is never loaded. ADCE alone treats the store as a root, marks %y, marks block a useful, and so marks the branch in entry (block a is control dependent on entry): nothing is removed. DSE's rule 2 deletes the store (the alloca never escapes and is never read). Now a contains only br, is not useful, and ADCE rewrites entry's branch to br label %j. The order matters: DSE → ADCE removes everything, ADCE → DSE leaves the empty diamond for SimplifyCFG.

4. Invariants and correctness¶

Lemma 17.3.8 (The marking computes the least sets)

Algorithms 17.3.2 and 17.3.5 terminate after \(O(I + U + \sum_B \lvert \mathrm{CD}(B) \rvert)\) steps and mark exactly \(\mathcal{U}\), respectively exactly \(\mathcal{L}\) and \(\mathcal{B}\).

Proof

Every instruction and block is marked at most once and pushed once; popping an instruction scans its operands (total \(U\)) and, for phis, its incoming blocks; marking a block scans \(\mathrm{CD}(B)\) once. Soundness of the marks: by induction on steps, each Mark/MarkBlock call applies one closure rule of Definition 17.3.1 or 17.3.4 to already-marked objects (or a root), so everything marked is in the least sets. Completeness: at termination the worklist is empty, so every marked instruction has had rule (3)/(4) applied, and every marked block rule (5) (applied inside MarkBlock); the marked sets are closed under all rules and contain the roots and the entry, so they contain the least sets.

Theorem 17.3.9 (Mark–sweep DCE preserves behavior)

Deleting every instruction outside \(\mathcal{U}\) (all branches roots) preserves the observable behavior of every run.

Proof

The CFG is unchanged because every terminator is kept. Compare a run of the original and of the new program on the same input: by induction on the number of executed steps, both follow the same block sequence and every kept instruction computes the same value. The step for a kept instruction \(I\): its operands are definitions in \(\mathcal{U}\) (closure), which by induction hold equal values; a deleted instruction has no side effect and its value is used only by deleted instructions (if a kept one used it, closure would have kept it). Branches are kept with equal conditions, so the block sequences agree; roots are kept with equal operands, so the observable behavior agrees.

Lemma 17.3.10 (Post-dominators are met in chain order)

Let \(X = p_0\) and \(p_{k+1} = \mathrm{ipdom}(p_k)\). On every path from \(X\) to an exit, the first occurrence of \(p_j\) precedes the first occurrence of \(p_{j+1}\).

Proof

Every \(p_j\) post-dominates \(X\), so each occurs. Suppose on some path the first \(p_{j+1}\) comes before the first \(p_j\). The prefix up to that \(p_{j+1}\) avoids \(p_j\). The suffix from \(p_{j+1}\) must contain \(p_j\) (the whole path does, and the prefix does not). If some path from \(p_{j+1}\) to the exit avoided \(p_j\), gluing it to the prefix would give a path from \(X\) avoiding \(p_j\), contradicting \(p_j \mathrel{\mathrm{pdom}} X\). So \(p_j \mathrel{\mathrm{pdom}} p_{j+1}\); also \(p_{j+1} \mathrel{\mathrm{pdom}} p_j\), and post-dominance is antisymmetric (Ch 15, Theorem 15.1.3 on the reverse CFG): \(p_j = p_{j+1}\), impossible for an immediate post-dominator.

Theorem 17.3.11 (ADCE preserves behavior of terminating runs)

Let every block reach an exit. After Algorithm 17.3.5, every run of the original function that terminates has a run of the new function with the same observable behavior; if moreover rule (6) is on or every loop terminates, runs correspond one to one.

Proof

Key claim: from a block \(X\) whose branch is dead, the next useful block after \(X\) on any terminating path is \(Y\), the nearest useful strict post-dominator of \(X\). Take a path \(X = w_0 \to w_1 \to \dots\) and let \(Z = w_k\) (\(k \geq 1\)) be its first useful block after \(X\). Suppose \(Z\) does not post-dominate \(X\). Let \(i < k\) be the largest index such that \(Z\) does not post-dominate \(w_i\) (\(i = 0\) qualifies). Then \(Z \mathrel{\mathrm{pdom}} w_{i+1}\) (\(w_{i+1} = Z\) when \(i + 1 = k\)), and \(Z\) does not post-dominate \(w_i\), so \(w_i \in \mathrm{CD}(Z)\) (Definition 17.3.3). Since \(Z \in \mathcal{B}\), rule (5) marked \(w_i\)'s terminator, so \(w_i \in \mathcal{B}\) (rule (3)); for \(i \geq 1\) this contradicts the choice of \(Z\), and for \(i = 0\) it contradicts "\(X\)'s branch is dead". So \(Z\) post-dominates \(X\) and is useful; by Lemma 17.3.10 the first useful post-dominator reached on the path is the nearest one in the chain: \(Z = Y\).

Phis. If \(Y\) has a live phi, rule (4) made every predecessor of \(Y\) useful; the block before \(Y\) on the path is then useful, so by the key claim it is \(X\) itself: the path uses the edge \(X \to Y\), which the rewrite keeps, and the phi selects the same operand. If \(Y\) has no live phi, the new edge's phi entries are irrelevant (dead phis are deleted).

Simulation. Consider a terminating run of the original. Restrict it to the useful blocks it visits, \(B_1, B_2, \dots\). The new program visits the same useful blocks in the same order: between consecutive useful blocks the original passes only non-useful blocks, whose branches are dead (a live branch would make its block useful); in the new program, a useful block with a live branch goes to the same successor (same condition value, by the data argument below), and one with a dead branch jumps to \(Y\), which is the next useful block by the key claim. Live instructions in useful blocks compute equal values by induction, since their operands are live (rule (3)) and phis select the same incoming operand. Roots are live, so observable behavior agrees. Termination: the key claim used that the original path reaches \(Y\). If the original run loops forever in non-useful blocks after \(X\), the new program jumps to \(Y\) and continues: a non-terminating run became terminating — a behavior change unless the language allows it (C++ forward progress, LLVM's mustprogress). Rule (6) prevents it: an infinite run repeats some cycle of the CFG, every cycle contains a retreating edge of the DFS, and rule (6) made that edge's source useful. So an infinite run visits useful blocks infinitely often, the next useful block \(Z\) after \(X\) always exists, and the key claim (which did not use termination) applies to it. (With dominance back edges instead of retreating edges this step fails on irreducible loops, which is why LLVM's adce finds the edges with a DFS.)

Theorem 17.3.12 (Dead-store elimination is sound)

Every store deleted by Algorithm 17.3.7 is dead (Definition 17.3.6), and deleting a dead store preserves observable behavior.

Proof

Rule 1: when store v, ℓ is deleted, a later store \(c\) in the same block with \(\mathrm{mustOverwrite}(c, \ell)\) is in Covered, and by the invariant no instruction between them may read a location aliasing \(c\) (such an instruction would have removed \(c\)), hence none may read \(\ell\) (a read of \(\ell\) reads bytes that \(c\) overwrites, which alias \(c\)); every path from the store passes the block's next instructions in order, so \(\ell\) is overwritten before any read. Rule 2: no instruction can read the alloca (its address does not escape, and no load or call reads it), and its lifetime ends at return. Behavior: a load returns the value of the last store to its bytes; for a dead store that is never the dead store on any path, so every load and every observable effect sees the same values.

What breaks it. Without the "every block reaches an exit" precondition the post-dominator tree needs a virtual exit and infinite loops have no post-dominators; LLVM marks their branches live up front (the §7 box on adce), and pebble-adce treats blocks that cannot reach an exit the same way (tests/ch17/lit/adce.ll, @forever). Without a sound side-effect model (a call assumed pure that writes memory) every DCE deletes observable behavior.

5. Complexity¶

\(I\) instructions, \(U\) operand uses, \(n\) blocks, \(e\) edges.

Technique	Time (worst)	Time (typical)	Space	Justification
Worklist DCE (Ch 13)	\(O(I + U)\)	linear	\(O(I)\)	each instruction deleted once, each deletion re-queues its operands
Mark–sweep DCE (17.3.2)	\(O(I + U)\)	linear	\(O(I)\)	Lemma 17.3.8 with no CD scans
ADCE (17.3.5)	\(O(I + U + n^2)\): \(\sum_B \lvert\mathrm{CD}(B)\rvert\) can be \(\Theta(n^2)\)	near-linear: LLVM computes only the needed part of the post-dominance frontier with an IDF calculator per batch of new useful blocks	\(O(I + n)\)	Lemma 17.3.8; the post-dominator tree costs \(O(e\,\alpha(e, n))\) (Ch 15)
DSE rule 1 (block-local) / MemorySSA DSE	\(O(I \cdot k)\) with \(k\) live `Covered` entries / \(O(I \cdot s)\) with a scan limit \(s\)	linear	\(O(I)\)	one backward scan per block; LLVM caps its walks (`-dse-memoryssa-scanlimit`)

Pathological family for control dependence. Nest \(n\) bottom-tested loops: \(E \to H_1 \to H_2 \to \dots \to H_n \to T_n\), where latch \(T_k\) branches back to \(H_k\) or on to \(T_{k-1}\), and \(T_1\) branches to \(H_1\) or to the exit \(X\). The innermost header \(H_n\) is control dependent on every latch \(T_1, \dots, T_n\) (each decides whether \(H_n\) runs again), and in general \(H_k\) and \(T_k\) depend on \(T_1, \dots, T_k\): \(\sum \lvert \mathrm{CD} \rvert = n(n+1)\), i.e. 6, 20, 72 and 272 pairs for \(n = 2, 4, 8, 16\) (computed with cfa.control_dependence). An ADCE that materializes \(\mathrm{CD}\) pays \(\Theta(n^2)\) on this family, which is why LLVM never builds it and asks an IDF calculator only about blocks that just became useful. At scale, ADCE and DCE are cheap enough that LLVM runs adce in every function simplification pipeline and GCC 14 runs dce/cddce eleven times at -O2 (gcc-14 -O2 -fdump-passes).

Kill cycles only (partial aggressiveness) — LLVM's adce-remove-control-flow=false keeps every branch: exactly Algorithm 17.3.2 [LLVM-ADCE]. Trade-off: no CFG changes, so dominator trees stay valid.
Loops that may not terminate — LLVM keeps back-edge branches unless -adce-remove-loops (§7 box); GCC's cddce first asks whether each loop is finite (finite_loop_p) and removes only finite ones [GCC-DCE]. Trade-off: soundness for C (no forward-progress guarantee in some cases) against deleting more code; mustprogress (C++, Rust) gives the license.
Partial dead code elimination — sink a computation into the branches that use it so it becomes dead on the others (Knoop–Rüthing–Steffen 1994, the dual of PRE; GVN-sink, Lesson 17.5 §6). Trade-off: code motion machinery.
Bit-level DCE — demanded bits (Lesson 17.2) deletes computations whose bits do not matter.
Dead argument and dead global elimination — the interprocedural versions (Ch 20).
Clean — the companion of Dead in EaC: fold redundant branches, remove empty blocks, merge and hoist after DCE [EaC3, Ch. 10]; Lesson 17.7 covers it as SimplifyCFG.

7. In real compilers¶

Mark–sweep DCE¶

LLVM's adce with -adce-remove-control-flow=false is mark–sweep DCE; GCC's plain dce passes are the same algorithm without control dependence (perform_tree_ssa_dce with aggressive = false, find_obviously_necessary_stmts for the roots) [GCC-DCE]. LLVM's dce pass is the trivially-dead worklist [LLVM-DCE].

Cycles: worklist DCE vs mark–sweep

Reproduce (clang 23.1.2, opt 23.1.2):

cat > dce.c <<'EOF'
int work(int n, int a) {
  int s = 0, t = 0;
  for (int i = 0; i < n; i++) {
    s = s + i;          // live: returned
    t = t + a * i;      // dead: never used after the loop
  }
  if (a > 5)
    t = t * 2;          // dead branch arm
  return s;
}
EOF
clang-23 -O0 -Xclang -disable-O0-optnone -fno-discard-value-names -S -emit-llvm dce.c -o dce.O0.ll
opt -passes=mem2reg -S dce.O0.ll -o dce.ll
opt -passes=dce -S dce.ll | grep -E 't\.0 =|add1 =|mul ='
opt -passes=adce -adce-remove-control-flow=false -S dce.ll | sed -n '/^for.end:/,/^}/p'

Output:

  %t.0 = phi i32 [ 0, %entry ], [ %add1, %for.inc ]
  %mul = mul nsw i32 %a, %i.0
  %add1 = add nsw i32 %t.0, %mul
for.end:                                          ; preds = %for.cond
  %cmp2 = icmp sgt i32 %a, 5
  br i1 %cmp2, label %if.then, label %if.end

if.then:                                          ; preds = %for.end
  br label %if.end

if.end:                                           ; preds = %if.then, %for.end
  ret i32 %s.0
}

What to notice: the worklist pass (dce) keeps the cycle %t.0/%add1 and %mul (each has a use); mark–sweep deletes them and %mul3, but keeps the branch on %cmp2 around the now empty if.then — the §3 mark–sweep trace.

Aggressive DCE¶

LLVM: llvm/lib/Transforms/Scalar/ADCE.cpp — AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences asks a ReverseIDFCalculator (the post-dominance frontier) for the dead terminators controlling newly live blocks; initialize marks back-edge branches live unless adce-remove-loops, and marks every block that cannot reach a return live; updateDeadRegions rewrites a dead branch to its successor with the largest post-order number of the reverse CFG, a cheap stand-in for "nearest post-dominator" [LLVM-ADCE]. GCC: gcc/tree-ssa-dce.cc — mark_control_dependent_edges_necessary in the cddce passes [GCC-DCE].

LLVM adce removes the dead branch; loops need permission

Reproduce (opt 23.1.2; dce.ll from the previous box):

opt -passes=adce -S dce.ll | sed -n '/^for.end:/,/^}/p'
cat > spin.ll <<'EOF'
define i32 @spin(i32 %n) {
entry:
  br label %loop
loop:
  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
  %i1 = add i32 %i, 1
  %c = icmp ne i32 %i1, %n     ; never false if n <= 0: may not terminate
  br i1 %c, label %loop, label %exit
exit:
  ret i32 0
}
EOF
opt -passes=adce -S spin.ll | sed -n '/^loop:/,/^exit:/p'
opt -passes=adce -adce-remove-loops -S spin.ll | sed -n '/^loop:/,/^exit:/p'

Output:

for.end:                                          ; preds = %for.cond
  br label %if.end

if.then:                                          ; No predecessors!
  br label %if.end

if.end:                                           ; preds = %for.end, %if.then
  ret i32 %s.0
}
loop:                                             ; preds = %loop, %entry
  %i = phi i32 [ 0, %entry ], [ %i1, %loop ]
  %i1 = add i32 %i, 1
  %c = icmp ne i32 %i1, %n
  br i1 %c, label %loop, label %exit

exit:                                             ; preds = %loop
loop:                                             ; preds = %entry
  br label %exit

exit:                                             ; preds = %loop

What to notice: the first output is the §3 ADCE result (LLVM leaves the unreachable if.then for SimplifyCFG). @spin computes nothing, but %c is never false when n ≤ 0, so deleting the loop could make a hanging program terminate: by default the back-edge branch is a root (rule (6)). With -adce-remove-loops the loop is removed — Theorem 17.3.11's termination assumption made explicit.

GCC cddce: marking through control dependence

Reproduce (gcc 14.2.0; dce.c from the first box):

gcc-14 -O2 -fdump-tree-cddce1-details -S dce.c -o /dev/null
grep -E 'Marking useful|Found loop|Deleting :|Removing basic' dce.c.*t.cddce1

Output:

Marking useful stmt: return s_11;
Found loop 1 to be finite: upper bound found.
Marking useful stmt: if (i_4 < n_8(D))
Deleting : t_14 = _1 + t_3;
Deleting : _1 = i_4 * a_9(D);
Deleting : if (a_9(D) > 5)
Deleting : t_3 = PHI <0(2), _14(3)>
Removing basic block 6

What to notice: the only root is the return; the loop test becomes useful because s is computed under it (control dependence), after GCC proved the loop finite — its version of rule (6). The dead cycle and the dead if (a > 5) are deleted, as in the ADCE trace of §3.

Dead stores and dead branches¶

LLVM: llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp — eliminateDeadStores walks MemorySSA from each store to find a killing store or prove no read follows [LLVM-DSE]; in the -O2 pipeline DSE runs right after ADCE [LLVM-Pipelines]. GCC has tree-ssa-dse.cc.

DSE unlocks ADCE

Reproduce (opt 23.1.2):

cat > inter.ll <<'EOF'
define i32 @inter(i32 %x, i1 %c) {
entry:
  %tmp = alloca i32
  br i1 %c, label %a, label %j
a:
  %y = mul i32 %x, 3
  store i32 %y, ptr %tmp       ; never loaded: a dead store
  br label %j
j:
  ret i32 %x
}
EOF
opt -passes=adce -S inter.ll | sed -n '/^entry:/,/^}/p'
opt -passes='dse,adce' -S inter.ll | sed -n '/^entry:/,/^}/p'

Output:

entry:
  %tmp = alloca i32, align 4
  br i1 %c, label %a, label %j

a:                                                ; preds = %entry
  %y = mul i32 %x, 3
  store i32 %y, ptr %tmp, align 4
  br label %j

j:                                                ; preds = %a, %entry
  ret i32 %x
}
entry:
  br label %j

a:                                                ; No predecessors!
  br label %j

j:                                                ; preds = %entry, %a
  ret i32 %x
}

What to notice: to ADCE the store is a root, which keeps %y and the branch; after DSE's rule 2 (a non-escaping alloca that is never read) deletes it, ADCE removes %y, the alloca and the branch. The two analyses are one fixed point that the pipeline approximates by ordering (Lesson 17.8).

Find where LLVM does it. In llvm/lib/Transforms/Scalar/ADCE.cpp, which command-line option decides whether branches that end a back edge are marked live at the start, and what is its default? (Quiz llvm-where-adce-loops.)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Mark–sweep DCE	Removes dead cycles; keeps every branch	\(O(I + U)\) · linear	CFG unchanged	Low	Cheap cleanup; LLVM `adce` without control flow, GCC `dce`
Aggressive DCE	Also removes dead branches and dead loops (Theorem 17.3.11)	\(O(I + U + \lvert\mathrm{CD}\rvert)\) · near-linear with IDF	Rewrites branches to post-dominators	Medium (post-dominators, control dependence, termination policy)	LLVM `adce`, GCC `cddce`, `pebble-adce`
Dead-store elimination	Removes overwritten / never-read stores; enables ADCE	\(O(I \cdot s)\) with MemorySSA scan limits	Deletes memory operations	High (alias analysis, partial overwrites)	LLVM `dse`, GCC `dse`

Choose mark–sweep DCE when the CFG must not change (between passes that keep dominator trees) and dead cycles are the target. Choose ADCE when you want dead control flow gone too, and you have post-dominators and a termination policy. Choose DSE when memory operations are the dead code; run it before ADCE so the branches it frees can go.

9. Assessment¶

Quiz: marksweep-dead, marksweep-cycles (tag marksweep-dce); adce-dead, adce-retarget, llvm-where-adce-loops (tag adce); dse-interplay, dse-rule (tag dse).
Drill: ./course drill adce-marking (hard compares with mark–sweep DCE). Dead-store elimination has no drill: its difficulty is alias reasoning, which Ch 19's drills cover; the quiz has an instance.
Flashcards: tags marksweep-dce, adce, dse.
Exercises: E2 pebble-adce.

References¶

See the chapter references.

Lesson 17.3 — Dead code elimination: mark–sweep, aggressive (control dependence), and dead stores¶

1. Problem and motivation¶

Mark–sweep DCE¶

Aggressive DCE¶

Dead stores and dead branches¶

2. Definitions and algorithms¶

3. Worked example¶

Mark–sweep DCE¶

Aggressive DCE¶

Dead stores and dead branches¶

4. Invariants and correctness¶

5. Complexity¶

6. Variants and refinements¶

7. In real compilers¶

Mark–sweep DCE¶

Aggressive DCE¶

Dead stores and dead branches¶

8. Comparison¶

9. Assessment¶

References¶