Finding missed optimizations through the lens of dead code elimination

Correctness bugs in compilers have a crisp test — wrong output — but missed optimizations had no oracle at all, so this paper builds one from dead code elimination by planting un-analyzable marker calls in every basic block; any marker one compiler deletes but another keeps is a pinpointed, reportable performance bug.

Why this problem is worth solving

Compiler correctness testing is a mature field with a devastating weapon: differential testing of program outputs. Generate a random program, run it under two compilers, and any output disagreement proves a miscompilation — automatically, at scale. (This site’s NNSmith explainer shows the same recipe applied to deep-learning compilers.) Compiler performance testing had no equivalent. A

Yet the bugs are real and consequential. They come from forgotten corner cases, from pass-ordering interactions (enabling more inlining can starve a later analysis), and from silent regressions — this paper finds 82 cases where older GCC or LLVM versions optimized code that current versions no longer can. Every such miss taxes every program compiled thereafter, invisibly.

What makes the problem approachable is choosing the right observable. The paper’s insight is that

What people did before, and where it broke

Benchmarking. The industry standard: run SPEC-class suites, watch for slowdowns. It detects regressions on those programs — not pre-existing misses, not programs outside the suite, and never with automatic localization to a culprit analysis.

Static-feature differential testing. Barany compared features of generated code (loads, spills) across compilers to flag potential misses — a symptom detector: a flagged file still requires manual archaeology to find what, where, and why.

Solver-backed analysis verification. Taneja et al. verified specific data-flow analyses against an SMT solver, finding real sharpness gaps — but one analysis at a time, with compiler modifications, by construction blind to interactions between passes.

The gap. Correctness testing thrives because its oracle is general, automatic, and black-box. Missed-optimization detection needed the same three properties, plus one more correctness testing gets for free: pointing at the location of the failure.

The idea

Make optimization quality observable. The marker construction is the load-bearing trick. A call to a function with no visible body is an information black hole: the compiler must assume it has arbitrary side effects, so no transformation may delete it — except proving the enclosing block unreachable, in which case deleting it is mandatory for any DCE worth the name. The marker thus converts an internal, invisible judgment (“is this block dead?”) into a persistent, external artifact (a call instruction present or absent), checkable with a text search. Property one: black-box — no compiler internals touched. Property two: general — because DCE consumes the results of alias analysis, constant and value-range propagation, inlining, CFG simplification, and more, a surviving dead marker indicts whichever of those failed, whatever it was.

Let compilers testify against each other — and themselves. With liveness verdicts in hand, differential testing does the rest. GCC eliminates a marker LLVM keeps: LLVM missed something (and vice versa — 2,637 finds in GCC, 318 in LLVM suggest which pipeline currently reasons more completely about this program class). Subtler and more damning: the same compiler at -O1 eliminating a marker that -O3 retains — more optimization producing worse analysis, usually a pass-interaction bug. And across versions: 44 GCC and 38 LLVM cases where an older release out-optimized the current one — true regressions, bisected to 23 and 21 unique culprit commits touching alias analysis, call-graph handling, CFG analysis, peephole rules, loop optimizations, pass management, and value-range analysis. The breadth of that list is the generality claim, demonstrated.

Point at the root, not the rubble. If block B is missed, every dead block dominated by B is “missed” too — noise for a bug reporter. The primary-marker definition (a missed block all of whose predecessors are alive or correctly eliminated) collapses each failure cascade to its frontier, which is where the responsible analysis gave up. This is what makes the output reportable: 84 reduced test cases filed, 62 already confirmed or fixed by GCC and LLVM developers — the practical-relevance receipt few testing papers can show.

Quantify the ideal. Because ground truth comes from execution, the method also measures absolute optimizer quality against a hypothetical perfect-DCE compiler: at -O3, GCC eliminates 94.40% and LLVM 95.69% of dead blocks — leaving 1.53% and 1.37% as primary misses. The pipeline is good; the residue is thousands of real bugs.

dead branch 1: needs alias analysis
dead branch 2: needs constant propagation

Why it works

• DCE sits downstream of most analyses → a dead block’s survival indicts whichever prerequisite failed → one simple oracle covers alias analysis to pass ordering, without naming any of them in advance.
• Undefined-function calls are un-analyzable by construction → their presence in assembly is an exact, tamper-proof record of the compiler’s liveness judgment → the oracle is black-box, portable across compilers, and needs zero compiler modification.
• Deterministic, inputless programs make liveness a fixed property → execution yields perfect ground truth → the method measures absolute quality (vs an ideal compiler), not merely relative disagreement.
• Differential testing across compilers, levels, AND versions multiplies the oracle → -O1-beats-O3 finds pass-interaction bugs, version diffs find regressions — classes invisible to benchmarks.
• Primary-marker filtering collapses failure cascades to their frontier → each find localizes a root cause → reduced cases are actionable, which is why developers confirmed or fixed 62 of 84.

What it costs

• Random-program bias. Csmith code is not application code; misses are found where random control flow lands, and the 86%/10% dead/alive mix is unrepresentative of real programs (helpfully so, for stress-testing DCE).
• DCE-visible misses only. Optimizations whose failure does not change block liveness — regalloc quality, vectorization width, scheduling — pass through the lens unseen.
• A “miss” is relative. Differential findings show one configuration beating another, not that eliminating the block is cheap or that fixing it is worthwhile; human triage (and 4–8-hour C-Reduce runs per case) stands between finds and reports.
• Marker perturbation. Inserting opaque calls inhibits some transformations around them; the measured pipeline is the instrumented program’s, slightly diverging from the pristine one.
• C-family scope. Demonstrated on GCC/LLVM with C; the concept ports, but each new language/compiler needs its instrumenter and corpus.

The evaluation

The corpus: 10,000 Csmith-generated C files, 3,109,167 instrumented basic blocks, compiled by GCC and LLVM across optimization levels and versions. The study answers three questions: how good are the optimizers absolutely, where do they disagree, and what do the disagreements teach.