Chapter 30 of 33

Code Optimization Techniques

On this page

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

  1. 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.

  2. 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.

  3. 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 -O0 to -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 + 1

Inside 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 + 1

CSE 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.14 becomes t = 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
    ret

At -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)  =>  x

Strength 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 / b out 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 L

3. 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: 25

The 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 if out 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 = 1 the compiler cannot assume *q is 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 become 2 * f(x) if f prints something or changes a global.

  • Floating-point arithmetic: it is not associative, so (a + b) + c cannot be reordered unless the programmer allows it (GCC's -ffast-math).

  • Exceptions and traps: moving a / b to where it executes more often can introduce a division-by-zero crash.

Optimization levels in GCC

Flag

Meaning

-O0

Default. No optimization; fastest compile and easiest debugging. Every variable lives in memory.

-O1

Basic optimizations that do not take much compile time.

-O2

Nearly all optimizations that do not trade space for speed. The usual choice for release builds.

-O3

Everything in -O2 plus more aggressive ones such as more inlining and loop vectorisation; code may grow.

-Os

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 + 1

Answers. (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).

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 + b after a = a + 1 is 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 printf is 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.