What must a dead-code elimination pass establish before it deletes a computation from a program?
answer
- two proofs, not one
- nobody reads the result
- nothing outside notices the work
- liveness runs backwards from exits
- an unseen call is assumed effectful
basics
~20 sTwo things, both required: nothing later reads the result, and the computation has no observable effect. Liveness analysis settles the first; effect reasoning settles the second. A statement with an effect stays even when its result is unused.
solid answer
~40 sDeletion needs two independent proofs. First, **the result is dead** — no path from that point reads the value before it is overwritten, which a backwards liveness analysis computes to a fixed point. Second, **removing the work changes nothing observable**: no write to storage anything else can read, no input or output, no fault the program relies on, no ordering operation whose whole point is that it happened. A call whose body the compiler cannot see is assumed effectful until it is inlined or summarised. Note that this is a different thing from unreachable code, which is code no path executes at all; most pipelines have a separate pass for that. Because deleting one statement can kill the liveness of its operands, the pass iterates.
go deeper
Recall that 'dead' means the result is never used again, and that this is not the same as code no execution path reaches.
Explain both conditions and the backwards liveness analysis, including why deleting one statement can make its operands dead and force the pass to iterate.
Show where the effect condition bites in production: escaped references blocking a dead-store removal, an overwrite of sensitive bytes vanishing, and values disappearing from a debugger in an optimised build.
Weigh the pipeline trade-off: how many cleanup rounds to buy, and what debuggability the team is prepared to lose in the build that ships versus the build it investigates incidents with.
## Two different things get called dead **Unreachable code** is code no execution path can reach: the arm of a branch whose condition folded to a literal, or statements after an unconditional transfer of control. Finding it is a reachability question over the control-flow graph, and most pipelines remove it in a separate step. **Dead code**, in the narrow sense this pass means, is code that *is* reached and *does* run, but whose result nothing afterwards observes. That is the harder case, because "nothing observes it" is two claims rather than one. | what it is | how it is found | typical remover | |---|---|---| | unreachable block | no path from entry reaches it | unreachable-code removal | | dead computation | result is never read again | dead-code elimination | | dead store | a later store overwrites it, unread between | dead-store elimination | | redundant computation | the same value is already available | common-subexpression removal | ## The two conditions 1. **No later use.** The value the statement defines must not be read on any path before it is overwritten. 2. **No observable effect.** Deleting the work must leave the program's visible behaviour identical. Both are required, and they are independent. A statement that writes to storage another party can read fails the second condition even when it plainly passes the first. ## Liveness, computed backwards A value is **live** at a point if some path from that point reads it before overwriting it. The analysis walks *against* the flow, starting from the exits: a use makes a variable live, a definition kills it, and at a join the sets from the successors are combined. Loops make it iterative, so the pass repeats until the sets stop changing. Once liveness is known, a definition whose target is not live immediately after it, and whose right-hand side is effect-free, can go. Deleting it removes uses of *its* operands, which may make them dead in turn — so the elimination itself iterates. This is exactly why elimination is scheduled after folding and propagation: those passes strand whole chains of assignments whose only consumer has just been replaced by a literal. ## What keeps a statement alive - **A write to storage outside the value's own private frame**, because something else may read it. - **Communication with the outside world** — reading or writing a stream, a device, a socket. - **A call whose body the compiler cannot see.** Conservatively assumed effectful; inlining it, or computing a purity summary for it, is what unlocks deletion. - **An operation that can fault** where the fault is part of the behaviour being relied on. - **An ordering or synchronisation operation**, whose entire purpose is that it executed at that point. The pass may still delete computations *around* such a statement — an unused value computed from its result, for example — without touching the statement itself. ## Dead stores and why aliasing matters If a location is written, then written again with no read in between, the first store is dead. Proving "no read in between" is where it gets interesting: the compiler must show that nothing else can reach that location, which is an aliasing question. If a reference to it has escaped — handed to a callee, stored in a structure, published to another thread — the compiler must keep the store. This has a practical consequence engineers meet in the wild: a loop that overwrites a buffer holding sensitive bytes just before the buffer goes out of scope is, to the compiler, a textbook dead store. Toolchains differ in what they offer here; several provide an explicit way to mark a store that must survive optimisation, and relying on the plain overwrite is a known trap. ## Where the pass sits, and what it costs a debugger Elimination is cheap and runs many times: after folding and propagation, after inlining, and again as a cleanup behind most heavyweight transforms, because each one leaves debris. The cost is paid at debugging time — a deleted computation means a value no longer exists to inspect at a breakpoint, and a variable can appear to hold nothing at all partway through a function. Toolchains differ in how much tracking metadata they carry to soften that, which is one of the reasons builds intended for debugging run a shorter pipeline.
- Why is dead-code elimination scheduled immediately after constant folding and propagation?Because that pair strands work. Once a use has been rewritten to a literal, the whole chain of assignments that produced the value has no consumer left, and the branch whose condition folded away leaves an arm nothing can reach. Elimination is the cheap cleanup that turns those simplifications into actually smaller code, so pipelines re-run it behind most transforms.
- What stops a compiler deleting a store to a buffer that is never read again?Aliasing. The compiler must prove nothing else can read that location, and if a reference to it has escaped into a callee, a data structure or another thread, it cannot. Where the location is provably private, the store is deletable — which is why overwriting sensitive bytes before a buffer goes out of scope is unreliable unless the toolchain offers an explicit way to pin the store.
saying these in an interview costs you the question
- Says a dead result is enough, ignoring observable effects.
- Confuses dead code with code no path ever reaches.
- Says any store whose value is never read again can be deleted.
- Assumes a call with an unknown body is safe to remove.
- Thinks liveness is computed forwards from the entry block.