Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 61 ยท Intermediate Code and Optimization

Loop and Global Optimizations

Learn loop-invariant code motion, strength reduction, loop unrolling, inlining and tail-call elimination, with runnable Python demonstrations.

Programs spend most of their time in loops, so a compiler gets the biggest return from improving them. A statement that runs a million times is worth a hundred statements that run once. Local optimizations clean up single blocks. The optimizations in this lesson look at loops and at whole functions, and most of them depend on the facts computed by data-flow analysis.

You will meet five techniques: loop-invariant code motion, strength reduction of induction variables, loop unrolling, function inlining and tail-call elimination. For each one you will see what it does, when it is allowed, and (in runnable code) what it saves. The demonstrations execute small three-address programs on a counting interpreter, so you can compare the work done before and after.

What counts as a loop

For the optimizer, a loop is a natural loop: a set of blocks with a single entry block (the header) that dominates every block in the set, plus a back edge from some block in the set to the header. Finding back edges needs the dominator information of the CFG: an edge N -> H is a back edge when H dominates N. Many transformations also create a preheader, a fresh block placed just before the header on the entry path. Code put there runs once, before the loop starts.

flowchart TD
    P["preheader<br/>(runs once)"] --> H["header<br/>if i #gt;= n"]
    H --> B["body"]
    B --> H
    H --> X["exit"]

A natural loop. The edge from the body to the header is the back edge. The preheader is the place to hoist invariant code.

Loop-invariant code motion

An instruction is loop-invariant if it computes the same value on every iteration. The standard rule: x = y op z is invariant when each operand is a constant, is defined only outside the loop, or is itself defined by one invariant instruction inside the loop (and x has a single definition in the loop). Find invariants by iterating until nothing new appears, then move them to the preheader.

Moving code is not always legal. Three conditions matter:

  • The instruction must have no side effects. Hoisting a print or a store to memory changes behavior.
  • It must not be able to fault when the loop would not have run it. If a loop body contains q = a / b guarded by if b != 0, hoisting the division above the test could divide by zero. Classic algorithms hoist only instructions that dominate every loop exit, or that cannot trap.
  • The destination must not be used before the instruction in the original order in a way that depends on the old value.

The next example hoists two invariant instructions out of a loop and then runs both versions to check that they print the same answer. The interpreter counts the instructions it executes.

Python Loop-invariant code motion

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.

With six iterations the hoisted program executes 10 fewer instructions: the two invariant instructions ran six times each before and once each after. The saving grows with the iteration count, and the answer (255) is identical. Note one subtle effect: if n were 0, the hoisted program would still compute t1 and t2 once. That is harmless here because they have no side effects.

Induction variables and strength reduction

A basic induction variable is a variable that changes by a fixed amount every iteration, like i = i + 1. A derived induction variable is a linear function of one, such as t = i * 4. Array indexing produces many of these: element i of an array of 4-byte numbers lives at base + i * 4.

Strength reduction replaces an expensive operation by a cheaper one. For induction variables it means: instead of multiplying i by 4 in every iteration, set t = 0 before the loop and add 4 to t each time i goes up by 1. Multiplication becomes addition. Further, if i is used only in the test and to compute t, the compiler can rewrite the test in terms of t and drop i entirely (induction variable elimination).

Loop unrolling

Each trip around a loop pays for a test and a jump in addition to the useful work. Unrolling repeats the body several times per trip, so the overhead is paid once for several iterations. It also gives the optimizer longer straight-line code to schedule and simplify. The cost is bigger code, which can hurt the instruction cache. If the iteration count is not known to be a multiple of the unroll factor, a compiler either keeps the exit test in every copy (as below) or adds a cleanup loop for the leftover iterations.

The second example applies strength reduction and then unrolling by four to a loop that sums the byte offsets i * 4, and compares the work of all three versions.

Python Strength reduction and unrolling

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.

All three versions print 19800, so the behavior is unchanged. Strength reduction removed all 100 multiplications. It did not reduce the instruction count (it even adds one initialization), because a multiplication and an addition both count as one instruction in this toy interpreter. On real hardware a multiplication can be several times slower than an addition, and that is the gain. Unrolling cut the taken jumps from 101 to 26 and the executed instructions from 505 to 430, because the jump back to top happens once for four iterations.

Inlining

Inlining replaces a call by a copy of the function body, with the arguments substituted for the parameters:

TEXT
function square(x):  return x * x          t = a + 1
y = square(a + 1)                    -->   y = t * t

The call overhead disappears (pushing arguments, jumping, setting up a stack frame, returning), but the bigger win is that the optimizer now sees the callee's code in the context of the caller. Constants flow into the body, branches fold away, and invariant calls can be hoisted. The price is code growth, so compilers inline using a cost model: tiny functions and functions called from only one place are cheap to inline, while recursive functions and huge bodies are not. Inlining is often called the "mother of all optimizations" because it enables so many others.

Tail-call elimination

A call is a tail call if its result is returned immediately, with nothing left to do in the caller afterwards. return f(x - 1, acc + x) is a tail call. return x + f(x - 1) is not, because the addition still has to happen after f returns. A tail call does not need a new frame: the caller's frame is no longer required, so the compiler can overwrite the parameters and jump to the start of the function. A self tail call then becomes an ordinary loop, and the stack never grows.

The third example uses a small expression language and two evaluators. The first creates a frame for every call and enforces a small stack limit of 100. The second rebinds the parameters and loops whenever the call is in tail position. It is a model of the transformation, not a real compiler, but the behavior is the one a compiler that eliminates tail calls produces.

Python Tail-call elimination turns recursion into a loop

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.

The plain evaluator handles sum_to(10, 0) with an 11-deep stack (ten recursive calls plus the first one), but crashes for 500. The loop version has no such limit and even sums a hundred thousand numbers. The non-tail sum_plain is the contrast: the addition after the call is still pending, so the frames must be kept, and the plain evaluator overflows. (To optimize such a function, a compiler or a programmer first rewrites it with an accumulator, which is exactly the sum_to form.)

Not every language promises this optimization. Scheme requires it, Kotlin and Scala support it for self-recursion in some cases, and most mainstream C and C++ compilers do it at higher optimization levels without a guarantee. Python never does, which is why deep recursion there ends in a RecursionError.

Loop jamming (fusion) and fission

If a program has two loops over the same range one after the other, the compiler can sometimes fuse them (also called loop jamming) into one loop that does both jobs:

TEXT
for i in 0..n: b[i] = a[i] * 2           for i in 0..n:
for i in 0..n: c[i] = b[i] + 1     -->       b[i] = a[i] * 2
                                              c[i] = b[i] + 1

Fusion saves one set of loop tests and jumps, and it improves locality: b[i] is used right after it is computed, while it is still in a register or in the cache. If b is not needed afterwards, the optimizer can even replace the array by a single temporary (scalar replacement) and drop the array traffic entirely. The opposite transformation, loop fission (splitting), is useful when one big body overflows the registers or the cache, or when one part can be vectorized and the other cannot.

Fusion is not always legal. The rule is about dependences: every iteration of the second loop must be able to run right after the matching iteration of the first. If the second loop reads b[i + 1], it needs a value that the first loop only produces in the next iteration. After fusion that value would not exist yet. The next program counts the work in both cases.

Python When fusion helps and when it breaks

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.

With b[i] the fused loop gives the same answer with half the loop tests (6 instead of 12). Scalar replacement then halves the reads and writes too (6 and 6 instead of 12 and 12), because the array b is never touched. With b[i + 1] the fused version silently computes [1, 1, 1, 1, 1, 0] instead of [3, 5, 7, 9, 11, 0]: it read b[i + 1] before it had been written. A compiler must therefore prove that no such dependence exists, and it also needs both loops to have the same trip count (or add guards, as the if above does).

More forms of code motion

Loop-invariant code motion is one member of a family of transformations that move code to a better place:

  • Loop unswitching moves a loop-invariant if out of a loop by duplicating the loop. for ... { if (flag) A else B } becomes if (flag) for ... { A } else for ... { B }. The test runs once instead of once per iteration, and each copy is simpler and easier to vectorize. The price is code size.
  • Code hoisting moves an expression that is computed on all paths leaving a branch up to the branch itself, so that it is written once. This uses the very busy expressions analysis. It saves code size, not time.
  • Code sinking is the opposite: it pushes a computation down into the only branch that uses it, so the other path does not pay for it.
  • Loop peeling executes the first (or last) iteration separately, which removes special cases from the main loop body.

All of them share the safety question from loop-invariant code motion: the moved code must not trap, and must not change what the program prints or stores.

Function cloning

Function cloning (also called specialization or multiversioning) makes a copy of a function that is tailored to a particular call. If a function is often called with the same constant for a parameter, the clone has that constant built in, and the tests that depended on it fold away. Compared with inlining, cloning keeps the call (so code is not duplicated at every call site) but still gives the optimizer a specialized body. The trade-off is the same as always: more code in exchange for faster code, so compilers clone only when they expect a real gain.

You already know cloning from another side: generics in C++ templates and Rust are implemented by cloning (monomorphization), with one copy of the code for each concrete type. Compilers also clone a function to create a version for a CPU feature (for instance with vector instructions) and pick the right one at start-up.

The program below clones a function for a fixed currency using Python's ast module. It substitutes the constant for the parameter, folds the comparisons, and drops the branches that can no longer be taken.

Python Cloning a function for a constant argument

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.

Each clone is much smaller than the original: the parameter and the whole if chain are gone, and the last line proves that the clone gives the same answer as the original called with "USD". The costs are the three extra functions, and the compiler needs to know at compile time that the argument is a constant. Real compilers clone based on profile information or on the kind of analysis you saw in data-flow analysis, which finds out what values a variable can hold.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. An instruction is loop-invariant when:

    Invariance depends on the operands: constants, values defined outside the loop, or values from other invariant instructions. Position in the body does not matter.
  2. 2. Why is hoisting a division out of a loop sometimes illegal?

    Code motion must not introduce new side effects or exceptions. A division guarded by a test inside the loop cannot be moved above the test.
  3. 3. What does strength reduction do for the derived induction variable t = i * 4?

    Because i increases by 1 each time, t increases by 4 each time. Maintaining t with t = t + 4 is cheaper than multiplying.
  4. 4. Which of these is a tail call?

    A tail call is the last action: its result is returned unchanged. In the first two the caller still has to add or multiply, and in the last it still has to print.
  5. 5. What is the main trade-off of loop unrolling?

    Unrolling cuts the per-iteration test and jump, but each copy of the body enlarges the code and can strain the instruction cache.

Summary

  • Loop fusion merges adjacent loops when no dependence blocks it; unswitching, hoisting and sinking move code; function cloning specializes a function for constant arguments.
  • Loops are the best place to optimize, since their bodies execute many times; natural loops have a header that dominates the body and a back edge.
  • Loop-invariant code motion moves computations that do not change inside the loop to a preheader, as long as it cannot add side effects or faults.
  • Strength reduction replaces multiplications on induction variables with additions; unrolling trades code size for less loop overhead.
  • Inlining removes call overhead and exposes the callee to the caller's optimizations, guided by a cost model.
  • Tail-call elimination reuses the caller's frame, turning self-recursion in tail position into a loop with constant stack space.

Next: Runtime Environments: Stack, Heap and Frames