Introduction
Programmers write code to be clear, not to be fast: they name intermediate values, repeat expressions, and leave computations whose results end up unused. An optimizing compiler cleans that up. The work happens on the IR, where each instruction is simple enough to reason about. Compilers such as GCC and Clang run dozens of passes; this lesson builds the classic ones for a basic block, a straight run of instructions with no jumps in or out.
How it works
The first pass goes forward through the block, keeping a table of what is known:
- Constant propagation and folding. After
a = 4, the table says a is 4.b = a * 2becomesb = 4 * 2, and folding computes it now:b = 8. - Copy propagation. After
e = c, later uses ofecan usecdirectly. - Algebraic simplification. Identities remove work:
x * 1 = x,x + 0 = x,x * 0 = 0,x - x = 0. - Common subexpression elimination. Remember every expression computed so far and where its result is. When
x + 8appears again, use the earlier result:d = c.
The second pass goes backward, to remove dead code. Start with the set of variables that are live at the end of the block, the ones the rest of the program needs. Walking backwards, keep an instruction only if it assigns a live variable; when it is kept, its destination stops being live (that value is now produced here) and the names it reads become live. Anything else computes a value nobody will read, so it is deleted.
These rules assume each variable is assigned once in the block, as in SSA form. With reassignments, the forward table must forget facts about a variable when it is assigned again, and any remembered expression that uses it.
Every optimization must keep the program's behaviour the same. Removing x = a / b when x is unused is only safe if dividing cannot fail; real compilers check such side effects carefully, and never remove output such as a print.
Syntax
for line in block: # forward: propagate and simplify
parts = [known.get(p, p) for p in operands]
...
for line in reversed(block): # backward: keep only what is needed
if dest in live: keep(line); live = live - {dest} | uses(line)
Example
FOLD = {"+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b}
def is_number(text):
return text.lstrip("-").isdigit()
def simplify(a, op, b):
if is_number(a) and is_number(b):
return str(FOLD[op](int(a), int(b)))
if op == "*" and "0" in (a, b):
return "0"
if (op in ("+", "-") and b == "0") or (op == "*" and b == "1"):
return a
if (op == "+" and a == "0") or (op == "*" and a == "1"):
return b
if op == "-" and a == b:
return "0"
return None
def propagate(code):
known, available, out = {}, {}, []
for line in code:
dest, expr = line.split(" = ")
parts = [known.get(p, p) for p in expr.split()]
if len(parts) == 3:
single = simplify(*parts) or available.get(tuple(parts))
if single is None:
available[tuple(parts)] = dest
else:
parts = [single]
if len(parts) == 1:
known[dest] = parts[0]
out.append(f"{dest} = {' '.join(parts)}")
return out
def remove_dead(code, live_out):
live, kept = set(live_out), []
for line in reversed(code):
dest, expr = line.split(" = ")
if dest in live:
kept.append(line)
live.discard(dest)
live |= {p for p in expr.split() if p.isidentifier()}
return kept[::-1]
block = [
"a = 4",
"b = a * 2",
"c = x + b",
"d = x + b",
"e = c * 1",
"f = e + d",
"g = y * 0",
"h = f - g",
"unused = h * 3",
]
step1 = propagate(block)
step2 = remove_dead(step1, live_out={"h"})
for title, code in [("before", block), ("after propagation, folding and reuse", step1), ("after dead code elimination", step2)]:
print(f"{title} ({len(code)} instructions):")
for line in code:
print(" ", line)Line by line
simplifyfolds two numbers and applies the algebraic identities; it returns the single value an instruction reduces to, or None.propagatereplaces known constants and copies, simplifies, and reusesavailableexpressions:d = x + bbecomesd = cbecausex + 8is already in c.- After the forward pass, most instructions are now constants or copies, and
his justf. remove_deadwalks backwards from the live variableh: it keepsh = f, which makes f live, thenf = c + c, which makes c live, thenc = x + 8.- Nine instructions become three, and h has the same value as before for every x and y.
Expected result
before (9 instructions):
a = 4
b = a * 2
c = x + b
d = x + b
e = c * 1
f = e + d
g = y * 0
h = f - g
unused = h * 3
after propagation, folding and reuse (9 instructions):
a = 4
b = 8
c = x + 8
d = c
e = c
f = c + c
g = 0
h = f
unused = f * 3
after dead code elimination (3 instructions):
c = x + 8
f = c + c
h = f
In the real world
GCC's -O2 and Clang's -O2 run these optimizations, and many more, over SSA-form IR. Clang's -O0 leaves them out, which is why debug builds are slower and easier to step through. JavaScript engines such as V8 apply the same ideas at run time to hot functions. The site Compiler Explorer (godbolt.org) shows the code different compilers produce at each level.
Common mistakes
- Removing an instruction with a side effect, such as a print or a call, because its result looks unused.
- Keeping stale facts after a variable is reassigned.
- Running dead code elimination forwards: whether a value is needed depends on what comes after it.
- Treating
a - bandb - aas the same expression; only+and*are commutative.
Best practices
- Write each optimization as a small pass, and run the passes in a loop while they still change something.
- Test that the optimized code gives the same results as the original on many inputs.
- Keep a copy of the unoptimized code and compare instruction counts to see what each pass achieved.
Summary
Constant folding and propagation, copy propagation, algebraic simplification and common subexpression elimination run forward through a block, replacing work with known results. Dead code elimination runs backward from the live variables and deletes instructions whose results are never read. Together they shrink code without changing what it does.
Quick check
Key takeaways
- Small rewrites, applied repeatedly, add up: each one exposes chances for the next.
- A forward pass propagates what is known; a backward pass finds what is still needed.
- An optimization must never change the program's observable behaviour.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.