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.