Optimizeimplementation

Dead Code Elimination

Delete an instruction only when it has no side effect AND no user. Both halves are required, and removing an effectful instruction because its value happens to be unused is a miscompilation rather than an optimization.

The question

The compiler deleted code I wrote. What did it have to prove first, and when does it get that wrong?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

IR in SSA form, plus one derived fact: the set of registers that are used by some remaining instruction or terminator. Liveness over SSA is what makes "does anything read this value?" answerable in one pass over the function — a question the AST could not ask, because in a tree the answer depends on scoping and aliasing rather than on def-use edges.

What this phase may assume or do

An instruction may be removed only if it has no side effect and its result has no remaining user. AtlasLang encodes exactly that as two conditions in one filter: hasEffect(i) must be false, and used.has(i.dest) must be false. hasEffect returns true for print, store, param and — importantly — every call, because the language has no purity annotation and assuming purity without proof is the specific miscompilation the predicate exists to prevent.

Key points

  • The rule is two conditions joined by AND: no side effect, and no remaining user. Dropping either half is a bug, and dropping the first one is a miscompilation.
  • A call with an unused result is not dead. Nothing about the value graph tells you what the callee does.
  • What counts as an effect is decided by the language, not by the optimizer, which is why purity annotations and effect systems exist at all.
  • DCE must be iterated or worklisted: removing one instruction is what makes the next one dead.
  • Aggressive DCE inverts the question — assume everything is dead unless it is effectful or feeds something effectful — and removes strictly more, including whole loops.

Two conditions, and only one of them is obvious

The obvious half is "nothing uses the result". If a value is computed and never read, computing it is wasted work and removing it changes nothing. Everyone gets that half right.

The half that produces miscompilations is "has no side effect". An instruction produces a value *and* may do something else — write memory, print, raise a signal, block, take a lock, fault. That second thing is not visible in the def-use graph at all. An optimizer that reasons only about values will conclude that a call whose result is discarded is dead, and delete a function that was doing all the actual work.

The transformation below is the canonical example, and it is deliberately arranged so that the naive rule gets it wrong. The first store to x genuinely is dead: a later store to the same location kills it on every path. The call that produced the stored value is not dead, however dead its result looks.

x = expensive(); x = 5; — one of these two lines can go, and it is not the one the value graph suggests
Before
%1 = call expensive()
store @x, %1
%2 = const 5
store @x, %2
%3 = load @x
print %3
After
%1 = call expensive()
%2 = const 5
store @x, %2
print 5
Legal only when

The first store @x is removed because a second store to the same location dominates every use of @x and overwrites it — the value can be observed by nothing. The call is kept because hasEffect is true for calls: its result is unused, but its *execution* may be observable, and the two are different questions.

Illegal when

Deleting %1 = call expensive() on the grounds that %1 has no user. If expensive prints, writes a file, mutates a global, increments a counter or takes a lock, the program's observable behavior changes and the compiler has produced a program that is not the one it was given. AtlasLang treats every call as effectful for precisely this reason, and a test compiles let ignored = noisy(5); print(1); and asserts the output is still 5 then 1.

What counts as an effect, and who is allowed to decide

implementationAtlasLang's hasEffect is four cases long, which is only possible because the language has no pointers, no threads, no exceptions and no foreign functions. LLVM answers the same question with a lattice of memory-effect attributes per function and per call site, refined by its interprocedural passes; GCC uses its own attribute set. The conservative default is identical in all three — an unannotated, unanalysed call is effectful.

The set of effectful operations is a property of the language, not of the optimizer. In AtlasLang it is print, store, param and call. In C it includes every volatile access, every write through a pointer that may be observed elsewhere, every library call the compiler has no model for, and — subtly — anything that might not terminate, because non-termination is observable behavior in C++ only under a rule that says loops without side effects may be assumed to finish.

The interesting cases are the ones where the language *grants* the compiler permission to assume no effect. C++ allows an implementation to elide allocations under specific conditions; C++ and C both allow copy elision to remove a constructor call with visible side effects, which is the rare case of a standard explicitly permitting an observable difference. Rust marks nothing pure but its type system means the compiler can often prove it; Haskell types the effects, so purity is checkable rather than assumed.

When a language cannot express purity, the compiler either assumes conservatively — AtlasLang's choice, and the safe one — or acquires it through attributes (__attribute__((pure)), __attribute__((const))), LLVM's readnone and nounwind), which move the proof obligation onto the programmer and make lying about it undefined behavior.

  • Observable, never removable: I/O, volatile access, synchronization, anything the language defines as sequenced against other observable actions — see [[observable-behaviour]].
  • Removable if unobserved: stores to memory nothing else can reach, which requires [[escape-analysis]] or [[alias-analysis]] to establish.
  • Removable if provably pure: a call whose callee the compiler has analysed, or which is annotated, or which is a library function with a built-in model. Interprocedural analysis is what upgrades a call from effectful to pure — [[interprocedural-analysis]].
  • Deliberately not removed by AtlasLang: every call. There is no purity annotation in the language and no interprocedural pass, so the conservative answer is the only sound one.

Why the pass runs more than once

Dead code elimination as written finds only the instructions that are dead *right now*. Removing them makes their operands unused, which makes their defining instructions dead, which makes the operands of those unused. A single sweep leaves most of the chain behind.

AtlasLang handles this the simple way: the pass manager runs the whole pipeline repeatedly until an iteration changes nothing, and reports how many iterations that took. Production compilers usually do the smarter thing — a worklist, seeded with the instructions whose operands just lost a user, so the cost is proportional to the change rather than to the function. Both converge on the same answer; the worklist version is why real DCE is close to linear.

There is a second, harder variant. *Aggressive* dead code elimination starts from the assumption that everything is dead except instructions with effects and the values they depend on, then marks backwards. It removes strictly more, including loops whose only purpose is to compute a value nobody reads, and it needs control-dependence information to decide when a branch itself becomes dead. The distinction matters when reading compiler output: code that survives simple DCE and vanishes at a higher level usually vanished to this.

Three iterations of the AtlasLang pipeline on let unused = 1 + 1; print(42);
After lowering
%1 = int 1 + 1
store @unused, %1
%2 = const 42
print %2
Fixed point
▸print 42

Read it asThe store dies first because nothing loads @unused; that leaves %1 with no user, so the addition dies on the next iteration. The print survives every iteration, because hasEffect returns true for it and the second condition is never even evaluated. A test asserts exactly this — that the arithmetic is gone and the print is not.

How it works

The steps, in the order the compiler takes them.

  • Walk every instruction and terminator, recording every register that appears as an operand. This is the used-set.
  • Walk the instructions again; for each, ask whether it has an effect. If yes, keep it unconditionally without consulting the used-set.
  • If it has no effect and defines a register, keep it only if the register is in the used-set.
  • Count what was removed; if anything was, the pass manager will run the pipeline again, because those removals shrank the used-set.
  • Repeat until an iteration removes nothing — the fixed point — and report the iteration count rather than assuming one pass sufficed.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

  • A logging call, a counter increment or a checksum verification disappears from a release build and not a debug build, and a bug that was being caught silently stops being caught. The optimizer decided the result was unused.
  • A busy-wait loop reading a hardware register is removed entirely, and the device driver hangs. The variable needed to be volatile; the compiler saw a load whose value nothing consumed.
  • A benchmark reports an implausible number because the loop body computed a value the harness never read, so the entire loop was removed. The classic fix is a compiler barrier or a DoNotOptimize helper — the symptom is a measurement that improves by orders of magnitude for no reason.
  • Security-sensitive code that zeroes a buffer before it goes out of scope has the memset removed, because nothing reads the buffer afterwards. The key stays in memory. This is common enough to have a dedicated function — explicit_bzero, SecureZeroMemory — whose entire purpose is to be undeletable.

When it helps

  • Cleaning up after every other pass. Most dead code in a real function was not written dead: inlining, specialization, propagation and branch simplification all produce it.
  • Removing the overhead of abstractions that compute more than the caller uses — a struct returned by value where the caller reads one field, a generic function where one branch is statically taken.
  • Reducing register pressure before allocation, because a value that is never computed never needs a register — see [[register-allocation]].

When it hurts

  • Where the effect was the point and the language could not express it. Zeroing memory, timing a loop, touching a memory-mapped register: all of these look dead and all of them need an explicit barrier or volatile to survive.
  • Debugging. A variable whose defining instruction was deleted has no location for the debugger to read, and reports as optimized out — which is [[debugging-optimized-code]] in its most common form.

What it costs

Every one of these is paid by something.

  • DCE buys removed instructions and reduced register pressure, and pays the cost of maintaining an accurate effect model. Every operation the compiler adds to the language needs an effect classification, and getting one wrong produces a silent wrong-code bug rather than a crash.
  • Being conservative about calls buys soundness and costs real optimization: AtlasLang cannot remove a genuinely pure computation that happens to be in a function, which is a large class of removable work in any language without an effect system.
  • Iterating to a fixed point buys completeness and pays compile time proportional to the depth of the dependence chain; a worklist buys that time back and costs the implementation complexity of maintaining the worklist correctly across other passes.

What else you could do

What a different compiler or language does instead, and when that is better.

  • Aggressive DCE (mark-and-sweep from effectful roots, using control dependence) removes more, including dead loops and dead branches, at the cost of needing a post-dominator tree — see [[dominator-tree]].
  • An effect system makes purity a checked property of the type rather than an assumption, so the compiler can delete calls soundly. Haskell and Koka do this; the cost is that every effectful function must say so in its signature — [[effect-systems]].
  • Purity attributes (__attribute__((const)), LLVM readnone) move the proof obligation to the programmer: cheap to add, and lying is undefined behavior with no diagnostic.
  • Linkers do a coarse version of the same thing at whole-program granularity: --gc-sections removes sections nothing references, which is dead code elimination with a function-sized unit and no need to understand any of the instructions — [[link-time-optimization]].

See it for yourself

The flag, dump or tool that shows you this directly.

  • Toggle dead-code elimination alone at /compilers/passes on let unused = 1 + 1; print(42); and watch the arithmetic go while the print stays.
  • clang -O2 -S -o - and look for the call you expected to see. If it is missing, add __attribute__((used)) or a volatile read and compare.
  • GCC: -fdump-tree-dce-details and -fdump-tree-cddce-details print exactly which statements each pass removed and why.
  • LLVM: opt -passes=dce -debug-only=dce on the IR shows the instructions being deleted one at a time.
  • To prove to yourself that a memset before free is removable: compile it at -O2, look at the assembly, then repeat with explicit_bzero and diff.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "Dead code is code you cannot reach." That is unreachable code, which is a different pass — AtlasLang has unreachable-block-elimination for it. Dead code is reachable code whose result nobody uses.
  • "If the optimizer removed it, it was useless." It was *unobserved by the model the compiler is allowed to use*. Memory-mapped registers, other threads and secret material are all observers the model does not include unless you tell it.
  • "The compiler will not delete my function call." It will, the moment it can prove the callee is pure — which after inlining and interprocedural analysis is often. The uncertainty is the point: rely on an annotation or a barrier, not on an assumption.

Misconceptions

The claim, and what is actually true.

An instruction whose result nobody reads is safe to delete.
Only if it also has no effect. That second condition is invisible in the def-use graph, and skipping it is how an optimizer deletes a print.
Writing to a variable makes the write survive.
A store that is overwritten before any read is dead by definition. If you need the write to happen — zeroing a key, poking a device — the language needs to be told, with volatile or a barrier.
Removing dead code makes the program faster in proportion to how much was removed.
Most of it was never executed on a hot path. The measurable wins are register pressure and code size; the reason the pass matters is that it is what lets every other pass be aggressive without leaving debris.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

If a computation produces a value nothing looks at, and doing it has no other consequence, the compiler removes it. The trap is the second half: some instructions do something besides producing a value, and those must stay even when the value is thrown away.

practical

When code disappears from a release build, ask what the compiler was allowed to assume about its effects. A call it can prove pure, a store to memory it can prove nobody else reads, a loop with no observable body — all removable. If you need one of them to survive, express that: volatile, an empty asm barrier, explicit_bzero, or a use the compiler cannot see through.

advanced

The pass is only as good as the effect model, and improving the effect model is where the real work is: alias analysis to prove a store is unobserved, escape analysis to prove an object never leaves a frame, interprocedural attribute inference to prove a call is pure. Aggressive DCE flips the direction — mark from effectful roots backwards through data *and control* dependence, so a branch whose both arms are dead is itself dead — and needs post-dominance to do so. That is also why it can delete an entire loop, which the forward formulation never can.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

implementationAtlasLang assumes every call is effectful because it has no purity annotation and no interprocedural analysis. LLVM and GCC both infer purity for many functions and are given it by attributes for others, so calls do get deleted there. Do not carry "my compiler never removes calls" from one to the other.
specIn C and C++, volatile accesses are observable behavior and may not be removed; in C++ specifically, a loop with no side effects may be assumed to terminate, which means an infinite empty loop is undefined behavior and can be deleted. Java and Rust make neither of those assumptions, so the same source shape survives in one language and vanishes in another.
typicalMainstream compilers combine DCE with other simplifications into one pass and run it many times through the pipeline, so attributing a specific removal to "the DCE pass" from the output alone is usually wrong. The dump flags above are the only reliable way to attribute it.

If you were asked this in an interview

  • Under what conditions may a compiler delete a function call whose return value is unused?
  • A colleague zeroes a password buffer before returning and the memset does not appear in the disassembly. What happened and how do you fix it?
  • Why does dead code elimination have to be run more than once, and what would you do instead of running it repeatedly?

Connections

Concurrencydata-races
Performancebenchmarkingmicrobenchmark-vs-system
Securitysecrets-managementpassword-storage