Imagine you ask a friend to buy milk, and they walk to the shop, come back, walk to the shop again for bread, and come back again. The job got done, but in a wasteful way. A good friend would buy both in one trip. A naive compiler is like the first friend: it translates each statement faithfully, one at a time, and the result is correct but full of repeated work.
The code optimizer is the phase that turns this faithful but clumsy code into code that does the same job with less work. In the earlier chapters on Intermediate Code & Three-Address Code and Basic Blocks & Flow Graphs we built the raw material; in DAG Representation of Basic Blocks we saw one way of cleaning up a single block. This chapter is the big tour of the classic optimizations.
Code optimization is the set of program transformations that make the generated code run faster, use less memory or energy, or take less space, while producing exactly the same observable behaviour as the original program.
The word "optimization" is a bit of a lie: compilers almost never produce the truly optimal program (finding it is undecidable in general). They produce an improved one. We will learn each technique with a small example, then apply them one after another to a real loop and count how much work disappears. Every transformed program in this chapter was run against the original by a small three-address-code interpreter to confirm it gives the same result, and the GCC outputs shown are real.
Three Rules Every Optimization Must Follow
Preserve meaning. The optimized program must produce the same output, the same side effects and the same errors for every input. A fast wrong program is worthless. This is why the optimizer must prove a transformation is safe, not just guess.
Improve on average. A transformation should make typical programs faster (or smaller). It may occasionally fail to help, but it should not usually make things worse.
Be worth the effort. Compile time matters too. An optimization that takes minutes to save a microsecond is not worth running by default. This is why compilers offer levels such as
-O0to-O3.
A fourth unofficial rule: look where the time goes. Programs spend most of their time in loops ("90% of the time in 10% of the code"), so loop optimizations give the largest gains.
Classifying Optimizations
By machine dependence
Point | Machine-independent | Machine-dependent |
|---|---|---|
Works on | Intermediate code (three-address code) | Target code or close to it |
Knows about | Values, variables, control flow | Registers, instruction set, costs, caches, pipelines |
Examples | Common subexpression elimination, constant folding, dead code elimination, loop-invariant code motion | Register allocation, instruction selection, peephole optimization, instruction scheduling |
Portable? | Yes, one implementation serves all targets | No, written per target |
By scope
Scope | Looks at | Typical tool |
|---|---|---|
Local | One basic block | DAG, value numbering |
Global (intraprocedural) | A whole function: all blocks and the flow graph | Data-flow analysis |
Loop | Loops inside the flow graph | Dominators, induction-variable analysis |
Interprocedural | Several functions together | Call graph, inlining |
Peephole | A small window of consecutive target instructions | Pattern matching |
Local optimizations are easy and safe because a block has no branches. Global ones are more powerful but need facts such as "is this value still the same here, whichever path we took?". Those facts come from Data-Flow Analysis, the next chapter. In this chapter we will reason about safety informally, and that chapter shows how the compiler proves it mechanically.
Function-Preserving Transformations
These four are the bread and butter of every optimizer. They do not change what is computed, only how often and where.
1. Common Subexpression Elimination (CSE)
An expression E is a common subexpression if it was computed before, and none of its operands has changed since. Then we can reuse the earlier result instead of computing it again.
Before After
t1 = 4 * i t1 = 4 * i
t2 = a[t1] t2 = a[t1]
t3 = 4 * i // same! t5 = t2 + 1
t4 = a[t3] // same!
t5 = t4 + 1Inside one block this is exactly what the DAG finds. Across blocks (global CSE), the compiler must know that the expression was computed on every path reaching this point and not killed on any of them. That property is called an available expression.
2. Copy Propagation
After a copy statement x = y, later uses of x can use y instead, as long as neither x nor y is changed in between. On its own this saves nothing, but it often turns the copy into dead code.
Before After copy propagation After dead code elimination
x = t3 x = t3 (x = t3 removed, if x is dead)
a[t2] = t5 a[t2] = t5 a[t2] = t5
y = x + 1 y = t3 + 1 y = t3 + 1CSE creates many copies (it replaces a recomputation by "use the old result"), and copy propagation cleans them up. The two are almost always used together.
3. Dead Code Elimination
A variable is live at a point if its current value may be used later; otherwise it is dead. A statement that computes a value which is never used is dead code and can be removed (provided it has no side effect like I/O or a function call that matters). Code that can never be executed at all is called unreachable code, and it can be removed too.
debug = false; // a constant the compiler can see
...
if (debug) { // condition is always false
print("value of x", x); // unreachable: removed
}Programmers rarely write dead code on purpose. It appears as a by-product of other optimizations (copy propagation, constant propagation, inlining) and of macros and generated code.
4. Constant Folding and Constant Propagation
Constant folding: evaluate an expression whose operands are all constants at compile time.
t = 2 * 3.14becomest = 6.28.Constant propagation: if a variable is known to hold a constant at some point, replace the variable by the constant. That often creates new folding opportunities, so the two alternate.
hours = 24 hours = 24
mins = hours * 60 ==> mins = 1440 (propagate 24, fold 24*60)
secs = mins * 60 secs = 86400 (propagate 1440, fold)Here is real GCC 15.2 output (x86-64, Intel syntax) for exactly this function:
int seconds_per_day(void) {
int hours = 24;
int mins = hours * 60;
return mins * 60;
}gcc -O0 gcc -O2
seconds_per_day: seconds_per_day:
endbr64 endbr64
push rbp mov eax, 86400
mov rbp, rsp ret
mov DWORD PTR -8[rbp], 24
mov eax, DWORD PTR -8[rbp]
imul eax, eax, 60
mov DWORD PTR -4[rbp], eax
mov eax, DWORD PTR -4[rbp]
imul eax, eax, 60
pop rbp
retAt -O2, both multiplications have disappeared: the answer 86400 was computed by the compiler. With a "debug flag" that is a constant 0, if (DEBUG) x = x * 100; return x + 1; compiled at -O2 to a single lea eax, 1[rdi] (that is, x + 1): the dead branch is gone.
Folding must follow the target language's arithmetic, not mathematics. If a constant expression overflows, or divides by zero, the compiler must not "fold" it into something the program would not do at run time. For floating point it must use the target's rounding rules.
Algebraic Simplification and Strength Reduction
Algebraic simplification uses identities to remove useless work:
x + 0 => x x * 1 => x x - x => 0 (integers)
x * 0 => 0 x / 1 => x -(-x) => xStrength reduction replaces an expensive operation by a cheaper one that gives the same result. Multiplication and division are slower than addition and shifts on most processors.
Expensive | Cheaper | Note |
|---|---|---|
x * 2 | x + x, or x << 1 | Safe for integers |
x * 8 | x << 3 | Safe for integers |
x2 (pow(x, 2)) | x * x | Avoids a library call |
x / 2 (unsigned) | x >> 1 | For signed x, C rounds toward zero but a shift rounds down, so the compiler must first add 1 to negative x before shifting |
x / 4.0 | x * 0.25 | Exact only because 0.25 is a power of two; x / 3.0 is not the same as x * (1/3.0) |
4 * i inside a loop where i increases by 1 | keep t, add 4 each iteration | Loop strength reduction (below) |
Loop Optimizations
To talk about loops we need to find them in the flow graph. Briefly: block D dominates block B if every path from the entry to B passes through D. An edge B → H where H dominates B is a back edge, and H is the loop header. The natural loop consists of H plus all blocks that can reach B without going through H. A preheader is a new empty block placed just before the header, so that code can be moved "out of the loop" into it and executed once.
1. Loop-Invariant Code Motion (Code Motion)
A computation is loop-invariant if it gives the same result every time round the loop: its operands are constants, or are defined only outside the loop, or are themselves loop-invariant. Such a computation can be moved to the preheader, so it runs once instead of n times.
Before After
while (i <= limit - 2) { t = limit - 2;
... /* limit not changed */ while (i <= t) {
} ...
}Moving a statement x = y op z out of a loop is safe when:
y op z is loop-invariant;
x is assigned nowhere else in the loop;
no use of x in the loop can see a different definition of x (for example, one from before the loop);
the statement's block dominates every loop exit, or x is not used after the loop. (Otherwise a loop that runs zero times would leave the wrong x.)
the computation cannot raise an error that the original program would not raise (moving
a / bout of a loop that never runs, when b is 0, would introduce a crash).
2. Induction Variables and Strength Reduction
A variable is an induction variable if it changes by a fixed amount every iteration. A basic induction variable is assigned only by i = i ± c in the loop. A derived induction variable is a linear function of one, like t = 4 * i or t = 4 * i + 8.
If i goes 0, 1, 2, ... then 4 * i goes 0, 4, 8, ... So instead of multiplying every time, keep t and add 4 whenever i increases by 1:
Before After
i = 0 i = 0
L: t = 4 * i t = 0 // 4 * initial i, in the preheader
...use t... L: ...use t...
i = i + 1 i = i + 1
if i < n goto L t = t + 4 // multiply became add
if i < n goto L3. Induction Variable Elimination
After strength reduction, i may be used only to count iterations and to test for the end. If t = 4 * i always, then i < n is the same test as t < 4 * n (for non-overflowing values). Compute 4 * n once in the preheader, test t instead, and delete i altogether if it is dead after the loop. Two variables that move in lock-step become one.
4. Loop Unrolling
Replicate the body k times and adjust the counter, so the loop test and jump happen k times less often:
for (i = 0; i < 100; i++) for (i = 0; i < 100; i += 4) {
a[i] = 0; a[i] = 0; a[i+1] = 0;
a[i+2] = 0; a[i+3] = 0;
}
tests: 101, increments: 100 tests: 26, increments: 25The cost is larger code, and when the trip count is not a multiple of k an extra "remainder" loop is needed. Besides saving tests, unrolling exposes several independent operations at once, which helps pipelined and superscalar CPUs.
5. Loop Fusion (Jamming) and Loop Fission
Fusion: two loops over the same range become one
for (i = 0; i < n; i++) a[i] = b[i] + 1; for (i = 0; i < n; i++) {
for (i = 0; i < n; i++) c[i] = a[i] * 2; ==> a[i] = b[i] + 1;
c[i] = a[i] * 2;
}Fusion halves the loop overhead and uses a[i] while it is still in the cache. It is legal here because iteration i of the second loop only needs a[i] from iteration i of the first. Fission (distribution) is the opposite: split one loop into two, for example to make each loop simple enough to vectorise, or to separate a part that has a dependence from a part that does not.
6. Other loop transformations (good to know names)
Loop interchange: swap inner and outer loops so a 2-D array is walked in memory order (row by row in C), which improves cache behaviour.
Loop unswitching: move a loop-invariant
ifout of the loop, creating two copies of the loop, one per branch.Loop peeling: pull out the first (or last) iteration so the remaining iterations become uniform.
Optimizations Across Functions
Inlining: replace a call by the body of the called function. It removes call overhead (saving registers, passing arguments, the jump and return) and, more importantly, lets the other optimizations see through the call. Cost: bigger code. Compilers inline small or single-use functions.
Tail-call / tail-recursion elimination: when the last action of a function is to call a function and return its result, the current activation record is no longer needed. A self-recursive tail call becomes a jump back to the start, turning recursion into a loop and saving stack space.
int gcd(int a, int b) { int gcd(int a, int b) {
if (b == 0) return a; start:
return gcd(b, a % b); // tail call if (b == 0) return a;
} int t = a % b; a = b; b = t;
goto start;
}Worked Example: Optimizing a Loop Step by Step
Here is a C loop over two int arrays (4 bytes per element), followed by its unoptimized three-address code. We assume i and k are not used after the loop.
s = 0;
for (i = 0; i < n; i++) {
k = x * y;
s = s + a[i] * k;
b[i] = a[i] + k;
} s = 0
i = 0
L1: if i >= n goto L2
t1 = x * y
k = t1
t2 = 4 * i
t3 = a[t2]
t4 = t3 * k
s = s + t4
t5 = 4 * i
t6 = a[t5]
t7 = t6 + k
t8 = 4 * i
b[t8] = t7
i = i + 1
goto L1
L2:Step 1: CSE and copy propagation. In the loop body, 4 * i is computed three times with i unchanged, so t5 and t8 can reuse t2. Then a[t5] is a[t2] and a has not been written in between (b is a different array), so t6 can reuse t3. Next, copy propagation replaces k by t1, and k = t1 becomes dead.
s = 0
i = 0
L1: if i >= n goto L2
t1 = x * y
t2 = 4 * i
t3 = a[t2]
t4 = t3 * t1
s = s + t4
t7 = t3 + t1
b[t2] = t7
i = i + 1
goto L1
L2:Step 2: loop-invariant code motion. x and y are never assigned in the loop, so t1 = x * y is invariant. Its block does not dominate the exit (the loop could run zero times), but t1 is a temporary not used after the loop, and integer multiplication cannot trap here, so the move is safe.
s = 0
i = 0
t1 = x * y // moved to the preheader
L1: if i >= n goto L2
t2 = 4 * i
... (rest unchanged)Step 3: strength reduction. i is a basic induction variable (i = i + 1) and t2 = 4 * i is derived from it. Initialise t2 = 0 before the loop and add 4 each time i is incremented.
Step 4: induction variable elimination. Now i is used only in the test i >= n. Since t2 = 4 * i, the test is equivalent to t2 >= 4 * n. Compute t9 = 4 * n in the preheader and delete i. The final code is:
s = 0
t1 = x * y
t2 = 0
t9 = 4 * n
L1: if t2 >= t9 goto L2
t3 = a[t2]
t4 = t3 * t1
s = s + t4
t7 = t3 + t1
b[t2] = t7
t2 = t2 + 4
goto L1
L2:We ran all five versions in an interpreter with random array contents for n = 0, 1, 5, 10 and 100: every version produced the same s and the same array b. Here is how many three-address instructions each executes:
Version | Instructions per iteration | Multiplications per iteration | Total for n = 100 |
|---|---|---|---|
Original | 14 | 5 (x*y, three 4*i, t3*k) | 1403 |
After CSE + copy propagation | 10 | 3 | 1003 |
After code motion | 9 | 2 | 904 |
After strength reduction | 9 | 1 | 905 |
After induction variable elimination | 8 | 1 | 805 |
Notice the strength reduction step: the count went up by one (an extra initialisation), but a multiplication in every iteration was replaced by an addition. Optimizations are about cost, not just instruction count. Overall the loop body shrank from 14 instructions with 5 multiplications to 8 instructions with 1 multiplication.
When the Compiler Must Not Optimize
Aliasing: if p and q might point to the same place, then after
*p = 1the compiler cannot assume*qis unchanged. Possible aliases block CSE, code motion and more.volatile variables in C (hardware registers, variables changed by signal handlers or other threads): every read and write must really happen, so none may be removed or merged.
Function calls with side effects:
f(x) + f(x)cannot become2 * f(x)if f prints something or changes a global.Floating-point arithmetic: it is not associative, so
(a + b) + ccannot be reordered unless the programmer allows it (GCC's-ffast-math).Exceptions and traps: moving
a / bto where it executes more often can introduce a division-by-zero crash.
Optimization levels in GCC
Flag | Meaning |
|---|---|
| Default. No optimization; fastest compile and easiest debugging. Every variable lives in memory. |
| Basic optimizations that do not take much compile time. |
| Nearly all optimizations that do not trade space for speed. The usual choice for release builds. |
| Everything in -O2 plus more aggressive ones such as more inlining and loop vectorisation; code may grow. |
| Optimize for size: -O2 minus options that typically increase code size. |
All Techniques at a Glance
Technique | What it removes | Main condition for safety |
|---|---|---|
Common subexpression elimination | Recomputing a value already available | Operands unchanged on every path since the earlier computation |
Copy propagation | Uses of a copy, then the copy itself | Neither side redefined between the copy and the use |
Dead code elimination | Computations whose results are never used; unreachable code | Result dead and no side effects |
Constant folding / propagation | Run-time arithmetic on known values | Same result as target arithmetic would give |
Algebraic simplification | Useless operations (x + 0, x * 1) | Identity holds for the data type |
Strength reduction | Expensive operators | Cheaper form is exactly equivalent |
Loop-invariant code motion | Repeating the same computation every iteration | Operands invariant; dominance / liveness conditions; no new traps |
Induction variable elimination | Redundant loop counters | Linear relation between variables; eliminated one dead after loop |
Loop unrolling | Loop test and branch overhead | Handle leftover iterations |
Loop fusion | Second loop's overhead; repeated memory traffic | Same bounds; no dependence violated |
Inlining | Call overhead; enables other optimizations | Code growth acceptable |
Tail-recursion elimination | Stack frames for recursive tail calls | Call is the very last action |
Solved Problems
Problem 1: Name the optimization
For each transformation, name the optimization.
(a) x = 3; y = x + 2; => x = 3; y = 5;
(b) for(...) { z = p * q; ... } => z = p * q; for(...) { ... } (p, q, z not changed in loop)
(c) y = x * 16 => y = x << 4
(d) t = b * c; ...; u = b * c => t = b * c; ...; u = t (b, c unchanged)
(e) x = y; z = x + 1 => x = y; z = y + 1Answers. (a) constant propagation followed by constant folding; (b) loop-invariant code motion; (c) strength reduction; (d) common subexpression elimination; (e) copy propagation (x = y may then become dead).
Problem 2: Is this code motion legal?
i = 0
L: if i >= n goto E
x = a / b
c[i] = x
i = i + 1
goto L
E: print(x)Can x = a / b be moved before the loop?
Answer. No, for two reasons. First, x is used after the loop (print(x)), and the statement does not dominate the exit: if n ≤ 0 the loop body never runs, and the original program prints the old x while the moved version prints a / b. Second, if b is 0 and n ≤ 0, the original never divides, but the moved version would crash.
Problem 3: Unrolling count
A loop for (i = 0; i < 64; i++) s += a[i]; is unrolled by a factor of 8. How many times is the loop condition evaluated before and after?
Answer. Before: 65 (64 true, 1 false). After: i takes values 0, 8, ..., 56 (8 true tests) plus the final false test: 9.
Problem 4: Induction variables
In the loop i = 1; L: j = 3 * i + 2; k = j * j; i = i + 2; if i < n goto L, which are induction variables?
Answer. i is a basic induction variable (+2 per iteration). j = 3i + 2 is a derived induction variable that grows by 6 per iteration, so j can be strength-reduced to j = j + 6 (with j = 5 before the loop). k = j * j is not an induction variable, because it is not a linear function of i.
Common Mistakes
Calling an expression common without checking operands.
a + baftera = a + 1is a new value.Moving code out of a loop that may run zero times, when the result is used after the loop or the code can trap.
Confusing code motion with strength reduction. Code motion moves a computation out of the loop; strength reduction keeps it in the loop but makes it cheaper.
Replacing signed x / 2 with x >> 1. For x = -3, C gives -1 but an arithmetic shift gives -2.
Applying math identities to floating point. x * 0 is not 0 for NaN or infinity; addition is not associative.
Thinking fewer instructions always means faster. Costs differ: one multiply may cost more than two adds, and unrolling adds instructions but runs faster.
Forgetting side effects when removing "dead" code: a call to
printfis never dead just because its return value is unused.
Interview and Exam Questions
What is the difference between machine-dependent and machine-independent optimization?
Machine-independent optimizations work on intermediate code and do not depend on the target (CSE, constant folding, code motion). Machine-dependent ones use knowledge of registers, instructions and costs of a particular machine (register allocation, instruction selection, peephole optimization, scheduling).
What is a loop-invariant computation?
One whose operands are constants, are defined only outside the loop, or are themselves loop-invariant, so it gives the same value on every iteration. It can be hoisted into the loop preheader if the safety conditions hold.
What is strength reduction? Give an example.
Replacing an expensive operation with an equivalent cheaper one: x * 2 by x + x, or a multiplication 4 * i in a loop by an addition t = t + 4 each iteration.
What are induction variables?
Variables that change by a constant amount each loop iteration. Basic induction variables are updated as i = i ± c; derived ones are linear functions c1 * i + c2 of a basic one.
Why is copy propagation useful if it doesn't remove anything by itself?
It replaces uses of x by y after x = y. Often x then has no uses left, so the copy becomes dead and is removed by dead code elimination.
What is the difference between dead code and unreachable code?
Dead code executes but its result is never used. Unreachable code can never execute because no path leads to it. Both can be removed.
What are the pros and cons of inlining?
Pros: no call/return overhead and the body can be optimized together with the caller's code (constants propagate in). Cons: larger code, which can hurt instruction-cache performance; recursive functions cannot be fully inlined.
Why can't the compiler always eliminate a[i] computed twice?
If something between the two reads may write to a[i] (an array store with an unknown index, a pointer store, or a function call), the value may have changed, so the second read cannot reuse the first.
Summary
Code optimization transforms a program to run faster or be smaller without changing its behaviour. It must be safe, usually profitable and worth the compile time.
Optimizations are machine-independent or machine-dependent, and local, global, loop, interprocedural or peephole in scope.
The core function-preserving transformations are CSE, copy propagation, dead code elimination, and constant folding/propagation; they feed each other.
Algebraic simplification and strength reduction replace operations by cheaper equivalents, as long as the identity holds for the data type.
Loop optimizations give the biggest gains: code motion, strength reduction of induction variables, induction variable elimination, unrolling, fusion and fission.
In our worked example the loop body went from 14 instructions with 5 multiplications to 8 instructions with 1.
Global optimizations need facts about all paths, such as which expressions are available and which variables are live. Computing those facts is the job of the next chapter, Data-Flow Analysis.