12.3 Dead Code Elimination

Dead code elimination (DCE) removes computations that cannot affect any observable program behavior. A value is not useful merely because it was computed; it must eventually contribute to a return, store, visible call, control decision, exception, volatile operation, or another required effect.

%a = load %input
%b = mul %a, 2
%dead = call @pure_expensive()
%unused = add %dead, 9
ret %b

If pure_expensive is truly pure and cannot trap, %dead and %unused are removable. %a and %b remain because they feed the return.

Mark useful instructions backward

In SSA form, DCE resembles mark-and-sweep garbage collection:

1. mark root instructions that are intrinsically observable or required;

2. follow each marked instruction's operands to their defining instructions;

3. repeat until no new definitions become marked;

4. remove unmarked instructions.

Typical roots include ret, externally visible stores, branches, calls with side effects, throwing operations whose exceptions are observable, volatile/atomic operations, and runtime bookkeeping required by the language. Debug builds may retain extra values for variable inspection, although debug metadata alone should not usually change release semantics.

“Unused result” does not mean dead

call print(x) is live even if it returns no used value. A bounds check is live when removing it would allow invalid memory access instead of the required exception. An integer division may be live because it can divide by zero. A volatile load may be an observable device read.

The pass needs trustworthy effect and trap information. A conservative compiler keeps an instruction whenever it cannot prove the instruction safe to erase. Incorrect effect annotations turn DCE from a cleanup pass into a source of miscompilation.

Unreachable code is a graph problem

Unreachable-block elimination starts from the function entry and marks every block reachable through feasible CFG edges. Unmarked blocks, their instructions, and outgoing edges can be deleted. Constant branches often expose this opportunity:

entry:
  br true, fast, slow
fast:
  ret 1
slow:               ; unreachable
  call @expensive()
  ret 2

Exception edges, indirect branches, coroutine resumes, and language-specific cleanup edges count as real control flow. A block that looks disconnected in the pretty printer may still be reachable through an exceptional successor. Conversely, a return closes its block; code textually following it must not gain a fake fallthrough edge.

DCE changes the graph around it

Deleting an instruction may make its operands unused, so DCE must operate recursively or use a worklist. Deleting an unreachable predecessor may simplify a phi node from several inputs to one. Removing a constant branch may expose another dead block. This is why optimizers often alternate SCCP, CFG simplification, phi simplification, and DCE until no profitable change remains.

Care is needed with infinite loops and nontermination. In some language semantics, replacing a definitely nonterminating loop with code after it changes behavior even when the loop produces no conventional output. Likewise, removing allocations may change observable failure behavior if out-of-memory is specified. The compiler's definition of “observable” comes from its language and optimization contract, not from intuition.

A robust test suite records both returned values and event traces. Include pure unused computations, unused effectful calls, trapping instructions, volatile reads, constant branches, exception edges, phi nodes with deleted predecessors, and nested unreachable regions. Always verify the repaired CFG after deletion.