Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 61 ยท Intermediate Code and Optimization

Local Optimizations

Learn local compiler optimizations inside a basic block: constant folding, algebraic simplification, strength reduction, CSE and dead code, with a runnable optimizer.

The three-address code from the last lessons is correct but wasteful. It computes 4 * 2 when it could just say 8, it calculates a + b twice, and it stores results nobody ever reads. An optimizer rewrites the code so that it does the same thing with less work. The name is generous: compilers do not find the best program, they apply many safe improvements that together make code noticeably faster or smaller.

The simplest improvements are local: they look at one basic block at a time. Inside a block, execution is a straight line, so you always know what happens in what order. That makes local optimizations easy to write and easy to prove correct. In this lesson you will write them one by one and combine them into a small optimizer that you can run and test.

The golden rule

An optimization is only allowed if it preserves the meaning of the program. Everything the program can observably do (the output it prints, the values it returns, the errors it raises, the files it writes) must stay the same. How fast it gets there is exactly what you are free to change.

Most of the work in compiler optimization is not finding the improvement, it is proving that it is safe. You will see several places in this lesson where an improvement that looks obvious breaks in a corner case.

Constant folding

If both operands of an operation are known numbers, do the arithmetic at compile time.

TEXT
t1 = 4 * 2      becomes      t1 = 8
t2 = 60 * 60    becomes      t2 = 3600

Constant folding is done in every compiler, and it is why you can write SECONDS = 24 * 60 * 60 for readability at no run-time cost. Two warnings: the folder must use the target's arithmetic (the size of integers and their overflow rules), and it must not fold an operation that would fail at run time, such as 1 / 0; that error belongs to the program's run, so the instruction must stay.

Constant and copy propagation

Folding needs known values. Constant propagation supplies them: after t1 = 8, a later use of t1 can be replaced by 8 (until t1 is reassigned). Copy propagation does the same for copies: after t6 = t2, uses of t6 can read t2 directly. Propagation also makes the copies themselves dead, so they can be deleted. Propagation and folding feed each other: replacing t1 by 8 in t2 = t1 + x gives t2 = 8 + x, and a later t3 = t2 - t2-style simplification becomes possible.

The bookkeeping rule is the important part. The compiler keeps a table of known facts (t1 = 8, t6 = t2). When a variable is assigned a new value, every fact that mentions it, on either side, must be forgotten.

Algebraic simplification and strength reduction

Some operations can be simplified using the algebra of numbers, without knowing the values:

Pattern Replace with
x + 0, 0 + x, x - 0 x
x * 1, 1 * x, x / 1 x
x * 0, 0 * x 0
x - x 0

Strength reduction replaces an operation by a cheaper one that gives the same result. The classic examples are x * 2 becoming x + x or x << 1, and x * 8 becoming x << 3. On older processors multiplication was many times slower than a shift, and even where it is not, the pattern shows up constantly in array indexing (multiplying an index by the element size).

Common subexpression elimination

If the same expression is computed twice and none of its operands changed in between, the second computation can reuse the first result. This is common subexpression elimination (CSE). In a basic block it is done with local value numbering: keep a table of expressions already computed, keyed by the operator and the operands.

TEXT
t1 = a + b                t1 = a + b
...                 ->    ...
t4 = b + a                t4 = t1

Two details make CSE trustworthy. First, + and * are commutative, so a + b and b + a must produce the same key (sort the operands). Second, when a variable is reassigned, every table entry that used it as an operand, or held its value, becomes invalid and is removed.

Dead code elimination

An assignment is dead if its result is never used before being overwritten. Removing it is free speed. The cleanest way to find dead assignments in a block is to walk it backwards, keeping the set of variables that are still needed (live): a print makes its argument live, an assignment to a variable that is not live can be deleted, and an assignment that survives makes its operands live.

Two notes. This pass needs to know which variables are still live when the block ends; our example block has none, but in a real function the live-out set comes from data-flow analysis. And removing an instruction that can have side effects (a function call, a division that might fail, a store through a pointer) needs extra care; here only prints have effects.

Unreachable code elimination

Dead code is code whose result is unused. Unreachable code is code that can never run at all. It appears after an unconditional goto or return, behind a condition that is always false (once constant folding has decided it), or under a label that no jump mentions. Programmers rarely write it on purpose; it is usually left behind by other optimizations, by macros, or by inlined functions.

The way to find it is to ask what can be reached. Start at the first instruction, follow every successor (the next instruction, plus the target of any jump, and nothing after a goto or return), and mark what you visit. Everything unmarked is unreachable and can be deleted, which makes the program smaller and the instruction cache happier. The same idea works on a control flow graph, where entire blocks with no incoming edge are dropped.

Python Marking and removing unreachable code

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Lines marked x are unreachable. Notice that orphan has a label and still dies: a label alone does not make code reachable, only a jump to it does.

Putting it together

The passes help each other, so optimizers run them repeatedly until nothing changes: a fixed point.

flowchart LR
    A["Fold and<br/>propagate"] --> B["Common subexpression<br/>elimination"]
    B --> C["Dead code<br/>elimination"]
    C --> D{"Did the code<br/>change?"}
    D -->|"yes"| A
    D -->|"no"| E["Done"]

Each pass creates opportunities for the others, so the loop runs until the code stops changing.

The optimizer below works on one basic block of TAC given as text. Study the sample block first: it contains a foldable 4 * 2, a multiplication by 8, an addition of zero, a multiplication by one, x + t1 which equals t2 only after propagation and operand reordering, a subtraction that turns out to be t2 - t2, and an unused x * x.

Python A local optimizer, pass by pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the block through the first round. Folding turns t1 = 4 * 2 into t1 = 8 and propagates it: t2 = 8 + x and t4 = x + 8. It also rewrites y * 8 as y << 3, turns t3 + 0 and t2 * 1 into plain copies, and propagates those copies into w = t3 + t2. Common subexpression elimination then notices that x + 8 is 8 + x (the sorted key) and replaces t4's computation with t4 = t2. Dead code elimination removes t1 (never read after propagation), t5, t6 and unused.

The second round is the interesting one. Propagating t4 = t2 into z = t4 - t2 gives z = t2 - t2, which the algebra rule reduces to z = 0, and print z becomes print 0. Without iterating to a fixed point, that simplification would be missed. Eleven instructions became five.

The last lines are a test, and it is the most important habit in this lesson. The program runs both versions on 1000 random inputs and compares the printed results. An optimizer bug is an extremely nasty kind of bug, because the compiler silently makes a correct program wrong. Every optimization you write should be checked against the original this way (the same idea is called differential testing, which compiler testing returns to).

When "obvious" rewrites are wrong

Optimizations depend on the exact rules of the language and the machine. These checks show three traps:

Python Rewrites that are safe, and rewrites that are not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

  • Multiplication by a power of two is a shift for every integer, so strength reduction is safe (as long as the shift count is in range for the machine).
  • Division by a power of two is a shift only if the language rounds toward negative infinity, like Python's //. C, C++, Java and most hardware truncate toward zero, so -7 / 4 is -1 but -7 >> 2 is -2. A compiler for those languages must add a correction for negative numbers, or only apply the shift when it can prove the value is non-negative.
  • Floating-point identities are mostly unsafe. x * 0.0 is 0.0 only if x is finite, x + 0.0 changes -0.0, and rearranging a sum such as (a + b) + c changes rounding. That is why compilers refuse to do this kind of algebra on floats unless you pass a flag such as -ffast-math, which knowingly gives up exactness.

An optimization that is wrong in one corner case is worse than no optimization. When you add a rule, ask: what happens with overflow, with zero, with negative numbers, with the largest value, with NaN? If you cannot answer, do not apply the rule, or test it exhaustively on a range as above.

Beyond one block

Local optimization is limited by the block boundaries. Everything the compiler learned in a block is forgotten at the next label, even if the previous block was the only way in. To carry facts across jumps, the compiler needs the whole control flow graph: that is data-flow analysis, which computes which definitions reach a point, which variables are still live and which expressions are already available. Those results enable the global versions of everything in this lesson, plus optimizations that only make sense across blocks, such as moving a calculation out of a loop (loop optimizations).

A common technique that stays local is peephole optimization: slide a small window (two to five instructions) over the final code and replace known inefficient patterns, like a store followed by a load of the same location, or a jump to the next instruction. Our tidy function from the TAC lesson was a peephole pass.

Where and when optimization is applied

Optimizations are named by how much of the program they look at, which is also how much they can know.

Scope Looks at Typical examples Cost
Local One basic block Constant folding, CSE, peephole Cheap, linear
Regional A loop, a branch or a few blocks Loop-invariant motion, unrolling Moderate
Global (intraprocedural) A whole function's flow graph Global constant and copy propagation, dead stores Needs data-flow analysis
Interprocedural Many functions or the whole program Inlining, cloning, link-time optimization Expensive, memory hungry

Two more questions decide what a compiler does. When? Machine-independent optimizations (the ones in this lesson) work on intermediate code, before the target is chosen; machine-dependent ones (instruction selection, register allocation, peephole on assembly, scheduling) run later. Working on intermediate code is what makes the optimizer portable: one optimizer serves every back end. How much? An optimization must be correct above all (the optimized program has to behave identically), it should usually pay for itself (smaller or faster code, sometimes lower energy use), and it must not make compile time unreasonable. That is why compilers offer levels such as -O0 (fast compile, easy debugging) up to -O3 (slow compile, fastest code), and why expensive whole-program passes are opt-in.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which rewrite is constant folding?

    Folding evaluates an operation on known constants at compile time. The first option is strength reduction, the third is dead code elimination and the fourth is common subexpression elimination.
  2. 2. Why does the CSE pass sort the operands of + and * when building its table key?

    Addition and multiplication give the same result in either order, so treating both orders as one key finds more repeated computations.
  3. 3. In which direction does the dead-code pass walk the block, and why?

    Whether an assignment is dead depends on the instructions after it. Walking backward lets the pass maintain the set of variables still needed.
  4. 4. Why is replacing x / 4 by x >> 2 not safe in a language that truncates division toward zero?

    For example -7 / 4 truncates to -1, but -7 >> 2 is -2. A shift matches floor division only.
  5. 5. Why does the optimizer repeat its passes until the code stops changing?

    Optimizations interact. Propagating a copy can expose a simplification that only a later pass can perform, so the compiler iterates to a fixed point.

Summary

  • Local optimizations rewrite one basic block at a time and must preserve the program's observable behavior.
  • Constant folding evaluates known operations at compile time; propagation passes known constants and copies forward; algebraic simplification and strength reduction replace operations with simpler or cheaper ones.
  • Common subexpression elimination uses a table of computed expressions (with commutative operands normalized) and invalidates entries when variables are reassigned.
  • Dead code elimination walks backward, keeping only assignments whose results are needed.
  • Passes feed each other, so an optimizer iterates to a fixed point, and every optimizer should be tested against the unoptimized program on many inputs.
  • Integer shifts, truncating division and floating-point arithmetic show why each rewrite needs its exact preconditions.

Next: Data-Flow Analysis