Course contentsShow
← Computer Science
Lesson 2066 of 2,87246. Compilation and InterpretationFree lesson

Loop-Invariant Code Motion

Moving computations that don't change inside loops to execute only once before the loop.

Loop-Invariant Code Motion

What you'll learn: You'll discover how compilers move unchanging computations out of loops to avoid redundant work on every iteration.


The Core Idea

Imagine you're making sandwiches for 100 people. You need to spread butter that's in the fridge. Would you walk to the fridge and back for every sandwich, or would you get the butter once before you start?

Loop-invariant code motion works the same way. When a compiler analyzes a loop, it looks for computations whose values don't change across iterations—these are loop invariants. Instead of recalculating them every time through the loop, the compiler moves (or "hoists") them to execute just once before the loop starts.

How It Works

Consider this pseudocode:

for i = 1 to 1000:
    x = y * z
    array[i] = x + i

If y and z don't change inside the loop, y * z produces the same result all 1000 times. The compiler can transform this to:

x = y * z
for i = 1 to 1000:
    array[i] = x + i

Now the multiplication happens once instead of 1000 times!

Safety Requirements

The compiler must verify:

  • The computation's inputs don't change within the loop
  • Moving the code won't alter program semantics (no side effects)
  • The computation would actually execute in the original loop (not inside a conditional that might skip it)

This optimization builds on constant propagation and common subexpression elimination concepts you've already learned, extending them specifically to loop contexts.

Key Takeaway: Loop-invariant code motion eliminates redundant work by moving computations that produce the same value every iteration to execute only once before the loop, significantly improving performance without changing program behavior.