Optimizing intermediate code

Advanced

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 * 2 becomes b = 4 * 2, and folding computes it now: b = 8.
  • Copy propagation. After e = c, later uses of e can use c directly.
  • 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 + 8 appears 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)
Open in compiler

Line by line

  1. simplify folds two numbers and applies the algebraic identities; it returns the single value an instruction reduces to, or None.
  2. propagate replaces known constants and copies, simplifies, and reuses available expressions: d = x + b becomes d = c because x + 8 is already in c.
  3. After the forward pass, most instructions are now constants or copies, and h is just f.
  4. remove_dead walks backwards from the live variable h: it keeps h = f, which makes f live, then f = c + c, which makes c live, then c = x + 8.
  5. 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 - b and b - a as 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

1. What does constant folding do to b = 4 * 2?
2. Which direction does dead code elimination walk the block?
3. c = x + 8 and later d = x + 8. What does CSE produce?
4. Why must an optimizer keep a print even if nothing reads its result?

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.