Common-Subexpression Elimination

Every compiler faces a simple but surprisingly common situation: the program asks for the same value more than once. Consider

x = a * b + c;
y = a * b - d;

The product $a \cdot b$ is computed in both lines. A naive compiler translates each line faithfully, running the multiplication twice. Common-subexpression elimination (CSE) notices that the two subexpressions are identical and the values of $a$ and $b$ have not changed between them, so it replaces the second computation with a reference to the result already sitting in a temporary register:

t = a * b;
x = t + c;
y = t - d;

One multiplication instead of two. The saving is trivial in isolation, but inside a tight loop that executes a million times, every eliminated operation matters.

CSE is one of the oldest and most studied compiler optimizations. Its roots trace back to John Cocke and the late 1960s, when the first optimizing compilers were being built. Today it appears in every serious compiler — GCC, LLVM/Clang, the JVM's JIT — applied automatically before the code ever reaches the CPU.

The demo below shows a small expression block. Click Step to let the CSE pass advance one step at a time, assigning value numbers and flagging repeated subexpressions. Click Run all to finish in one go, or Reset to start over with a fresh example.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div id="code-block" class="code-block"></div>
<div id="status" class="status"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.code-block { font: 14px ui-monospace, monospace; background: #f4f6f8;
  border: 1px solid #cdd9e3; border-radius: 8px; padding: .7rem .9rem;
  margin-bottom: .6rem; line-height: 1.7; }
.line { display: flex; align-items: baseline; gap: .5rem; padding: 1px 0; border-radius: 4px; transition: background .15s; }
.line.active { background: #fff3cd; }
.line.elim { background: #d4edda; }
.lnum { color: #999; font-size: .8em; min-width: 1.4em; text-align: right; user-select: none; }
.lcode { flex: 1; white-space: pre; }
.badge { font-size: .72em; padding: .1em .45em; border-radius: 4px; margin-left: .4rem; font-family: system-ui, sans-serif; font-weight: 600; }
.badge-new { background: #cfe2ff; color: #084298; }
.badge-reuse { background: #d1e7dd; color: #0a3622; }
.vnum { color: #6f42c1; font-weight: 700; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin-bottom: .5rem; }
.status.info { color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

// Code not found

Notice that CSE works by assigning each unique computed value a value number. Two subexpressions get the same value number when they produce the same result — that is the signal that the second occurrence is redundant and can be replaced. The key insight is that structural identity (same operator, same operands in the same order, same value numbers) is a sufficient condition for value identity, as long as no intervening assignment changes an operand.

CSE comes in two flavors with very different costs.

Local CSE works inside a single basic block — a straight-line sequence of instructions with no branches. Value numbering sweeps through in a single pass, assigning numbers and detecting duplicates. The whole procedure runs in $O(n)$ time (with hashing). This is the fast, simple version every compiler does.

Global CSE looks across basic block boundaries. An expression $a \cdot b$ computed in one branch of an if statement might make another computation in a later block redundant. Finding such opportunities requires dataflow analysis — computing which expressions are available at the entry of every basic block. The classic algorithm (from Kildall, 1973) iterates to a fixed point on a lattice of expression sets. It runs in polynomial time and is well understood, but it is more expensive than the local pass and requires the program-synthesis-era machinery of control-flow graphs.

A subtler variant, partial redundancy elimination (PRE, Morel & Renvoise 1979), subsumes both CSE and loop-invariant code motion in a single framework. PRE is also a solved problem — the optimal algorithm runs in polynomial time — but its analysis is sophisticated enough that many production compilers use approximations.

The bottom line: CSE in all its forms is a solved optimization problem. Unlike integer programming or scheduling, there is no NP-hardness lurking here — the challenge is engineering efficiency, not computational intractability.

CSE is not just an abstract exercise — it appears in the hot path of nearly every real software system:

• Scientific computing: tight numerical loops often recompute the same index expression $i \cdot \text{stride} + \text{offset}$ on every iteration. CSE and loop-invariant code motion together can cut the operation count dramatically.
• GPU shader compilation: graphics drivers compile shaders at runtime. The driver's compiler has only milliseconds to optimize millions of shader invocations, so cheap, effective passes like CSE are critical.
• Database query engines: query planners build expression trees that share subexpressions across predicates. Recognizing that price * 0.9 appears in both the WHERE clause and the SELECT list avoids evaluating it twice per row.
• JIT compilers: the JVM and V8 apply CSE constantly on hot bytecode paths, amortizing the cost over many executions.
• Hardware synthesis: register-transfer-level (RTL) optimizers apply CSE to logic expressions before mapping them to gates, reducing transistor count.

The unifying theme is always the same: identical work should happen once. CSE makes that principle mechanical and automatic.

Common-subexpression elimination is deceptively simple — spot the duplicate, keep one copy, throw away the rest. Yet that simplicity hides a deep principle: identity of value implies identity of effort, and no effort should be duplicated.

The idea scales from a two-line code snippet to an entire program. Local CSE handles the easy cases in a single linear sweep; global CSE and PRE extend it across control flow with dataflow analysis; and modern compilers chain all three together without the programmer ever noticing. The result is code that does less work without being any harder to write.

If you want to understand how compilers think about programs, CSE is one of the best entry points. It touches value numbering, control-flow graphs, dataflow lattices, and the broader world of program-synthesis and optimization — all in a package whose core idea fits in a single sentence: compute once, use many times.