Loop optimization (invariant code motion) in Compiler Design - Full Explanation

Introduction

Loops often repeat the same calculations many times, which wastes time. Finding parts of the loop that do not change and moving them outside can make programs run faster and use less power.

Explanation

Loop Invariant Code

Loop invariant code refers to calculations or expressions inside a loop that produce the same result every time the loop runs. These do not depend on the changing parts of the loop, so they can be safely moved outside without changing the program's behavior.

Loop invariant code does not change during loop execution and can be moved outside the loop.

Invariant Code Motion

Invariant code motion is the process of identifying loop invariant code and moving it before the loop starts. This reduces the number of times the code runs, improving performance by avoiding repeated work.

Moving invariant code outside the loop saves repeated calculations and speeds up execution.

Safety Checks

Before moving code, the compiler must ensure that the code does not depend on variables modified inside the loop and that moving it won't change the program's results. This includes checking for side effects like function calls or memory changes.

Invariant code motion must only move code that is safe and does not affect program correctness.

Benefits of Invariant Code Motion

By reducing repeated work inside loops, programs run faster and use less CPU power. This optimization is especially helpful in loops with many iterations or complex calculations.

Invariant code motion improves efficiency by cutting down unnecessary repeated computations.

Real World Analogy

Imagine packing for a trip where you need to fold your clothes every day. If some clothes don't change, like your shoes, you pack them once before the trip instead of folding them daily. This saves time and effort during the trip.

Loop Invariant Code → Shoes that don't need folding every day

Invariant Code Motion → Packing shoes once before the trip instead of daily

Safety Checks → Making sure shoes are clean and ready to pack before the trip

Benefits of Invariant Code Motion → Saving time and effort during the trip by packing once

Diagram

Diagram

┌───────────────────────────────┐
│           Loop Start           │
├───────────────────────────────┤
│  [Invariant Code]              │ ← Moved outside loop
├───────────────────────────────┤
│  Loop Body:                   │
│   - Code that changes each    │
│     iteration                 │
└───────────────────────────────┘

Diagram showing invariant code moved outside the loop to run only once before the loop starts.

Key Facts

Loop Invariant Code → Code inside a loop that produces the same result in every iteration.

Invariant Code Motion → Optimization that moves loop invariant code outside the loop to reduce repeated execution.

Safety Checks → Verifications to ensure moving code outside the loop does not change program behavior.

Performance Improvement → Reducing repeated calculations inside loops speeds up program execution.

Code Example

Compiler Design

def compute_sum(arr, n):
    total = 0
    factor = 2 * 3  # Invariant calculation
    for i in range(n):
        total += arr[i] * factor
    return total

# Optimized version with invariant code motion
def compute_sum_optimized(arr, n):
    total = 0
    factor = 2 * 3  # Moved outside the loop
    for i in range(n):
        total += arr[i] * factor
    return total

arr = [1, 2, 3, 4]
print(compute_sum(arr, len(arr)))
print(compute_sum_optimized(arr, len(arr)))

Common Confusions

Believing all code inside a loop can be moved outside safely.

Believing all code inside a loop can be moved outside safely. Only code that does not depend on variables changed inside the loop and has no side effects can be moved.

Thinking invariant code motion changes what the program does.

Thinking invariant code motion changes what the program does. Invariant code motion preserves program behavior by only moving safe code outside the loop.

Summary

Loop invariant code is code inside a loop that does not change during iterations.

Invariant code motion moves such code outside the loop to avoid repeated work.

This optimization improves program speed while keeping results the same.

Practice

1. What is the main goal of loop optimization (invariant code motion) in compiler design?

easy

A. To move calculations that do not change outside the loop to improve efficiency

B. To increase the number of loops in the program

C. To add more calculations inside the loop for accuracy

D. To remove all loops from the program

Solution

1. Step 1: Understand loop invariant code

   Loop invariant code means calculations inside a loop that produce the same result every time.

2. Step 2: Purpose of moving invariant code

   Moving such code outside the loop avoids repeating the same calculation, saving time.

3. Final Answer:

   To move calculations that do not change outside the loop to improve efficiency -> Option A

4. Quick Check:

   Invariant code motion = move unchanging code outside loop [OK]

Hint: Move unchanging calculations outside loops to speed up code [OK]

Common Mistakes:

• Thinking loop optimization adds more loops
• Believing invariant code should stay inside loops
• Confusing optimization with removing loops

2. Which of the following code snippets correctly applies invariant code motion?

easy

A. for i in range(n):
x = 5 * 3
print(i + x)

B. for i in range(n):
x = i * 3
print(x)

C. for i in range(n):
print(i + 5 * 3)

D. x = 5 * 3
for i in range(n):
print(i + x)

Solution

1. Step 1: Identify invariant calculation

   The calculation 5 * 3 does not depend on the loop variable i, so it is invariant.

2. Step 2: Check code placement

   x = 5 * 3 for i in range(n): print(i + x) moves 5 * 3 outside the loop, calculating it once before looping.

3. Final Answer:

   x = 5 * 3 for i in range(n): print(i + x) -> Option D

4. Quick Check:

   Invariant code outside loop = x = 5 * 3 for i in range(n): print(i + x) [OK]

Hint: Put constant calculations before the loop starts [OK]

Common Mistakes:

• Calculating invariant code inside the loop repeatedly
• Moving variable-dependent code outside the loop
• Ignoring the loop variable dependency

3. Consider the following code snippet:

sum = 0
for i in range(1, 5):
    x = 10 * 2
    sum += i + x
print(sum)

What will be the output after applying invariant code motion optimization?

medium

A. 50

B. 70

C. 90

D. 110

Solution

1. Step 1: Move invariant calculation outside loop

   Calculate x = 10 * 2 = 20 once before the loop.

2. Step 2: Calculate sum with optimized code

   sum = 0; loop i=1 to 4: sum += i + 20
   Sum = (1+20)+(2+20)+(3+20)+(4+20) = 21+22+23+24 = 90

3. Final Answer:

   90 -> Option C

4. Quick Check:

   Sum of (i+20) for i=1 to 4 = 90 [OK]

Hint: Calculate constants once, then sum loop values [OK]

Common Mistakes:

• Adding 10*2 inside loop each time
• Miscounting loop iterations
• Forgetting to add i in sum

4. Identify the error in the following code related to invariant code motion:

for i in range(3):
    y = i * 2
    x = 4 + 5
    print(x + y)

What is the problem if we move x = 4 + 5 inside the loop?

medium

A. Moving x inside loop causes repeated calculation, reducing efficiency

B. x depends on i, so moving it outside causes error

C. No problem, code is optimized correctly

D. x is undefined inside the loop

Solution

1. Step 1: Analyze variable dependency

   x = 4 + 5 is invariant; it does not depend on i.

2. Step 2: Effect of moving x inside loop

   Moving x inside loop causes repeated calculation each iteration, wasting resources.

3. Final Answer:

   Moving x inside loop causes repeated calculation, reducing efficiency -> Option A

4. Quick Check:

   Invariant code inside loop = inefficient [OK]

Hint: Keep invariant code outside loop to avoid repeats [OK]

Common Mistakes:

• Thinking invariant code depends on loop variable
• Believing repeated calculation improves speed
• Confusing variable scope with optimization

5. Given the nested loop below, which is the best way to apply invariant code motion to optimize it?

for i in range(3):
    for j in range(4):
        x = 2 * 3
        y = i + j
        print(x + y)

hard

A. Move both x and y outside all loops

B. Move x outside both loops, keep y inside inner loop

C. Keep both x and y inside inner loop

D. Move y outside inner loop, keep x inside inner loop

Solution

1. Step 1: Identify invariant expressions

   x = 2 * 3 is invariant (does not depend on i or j). y = i + j depends on both loop variables.

2. Step 2: Apply invariant code motion

   Move x outside both loops to calculate once. y must stay inside inner loop as it changes each iteration.

3. Final Answer:

   Move x outside both loops, keep y inside inner loop -> Option B

4. Quick Check:

   Invariant x outside loops, variable y inside loop [OK]

Hint: Only move calculations independent of all loops outside [OK]

Common Mistakes:

• Moving variable-dependent code outside loops
• Keeping invariant code inside loops unnecessarily
• Confusing which variables depend on loop indices