Loop optimization (invariant code motion) in Compiler Design - Step-by-Step Execution

Concept Flow - Loop optimization (invariant code motion)

Start Loop

↓

Identify Invariant Code

↓

Move Invariant Code Outside Loop

↓

Execute Loop Body Without Invariant Code

↓

Loop End

↓

Repeat or Exit

The process finds code inside a loop that does not change and moves it outside to run once, improving efficiency.

Execution Sample

Compiler Design

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

This loop calculates 5*2 inside each iteration, but since 5*2 is always 10, it can be moved outside the loop.

Analysis Table

Iteration	i	Expression '5 * 2' Computed?	Value of x	Action	Output
1	0	Yes	10	Calculate x inside loop	0 + 10 = 10
2	1	Yes	10	Calculate x inside loop	1 + 10 = 11
3	2	Yes	10	Calculate x inside loop	2 + 10 = 12
				Optimization: Move 'x = 5 * 2' outside loop
1	0	No (moved outside)	10	Use precomputed x	0 + 10 = 10
2	1	No (moved outside)	10	Use precomputed x	1 + 10 = 11
3	2	No (moved outside)	10	Use precomputed x	2 + 10 = 12
				Loop ends after 3 iterations

💡 Loop ends after 3 iterations as i reaches 3, condition i < 3 is False

State Tracker

Variable	Start	After 1	After 2	After 3	Final
i	undefined	0	1	2	3 (loop exit)
x	undefined	10	10	10	10 (constant after optimization)

Key Insights - 3 Insights

Why can 'x = 5 * 2' be moved outside the loop?

Because '5 * 2' always equals 10 and does not depend on the loop variable 'i', so computing it once before the loop saves repeated work (see execution_table rows 1-3 vs 5-7).

Does moving invariant code outside the loop change the output?

No, the output remains the same because the value of 'x' is constant and used in the same way inside the loop (compare outputs in execution_table rows 1-3 and 5-7).

What happens if the code depends on the loop variable?

If the code uses the loop variable or changes each iteration, it cannot be moved outside because its value changes every time (not invariant).

Visual Quiz - 3 Questions

Look at the execution_table, at iteration 2 before optimization, is '5 * 2' computed inside the loop?

A No, it is computed only once

B Yes, it is computed every iteration

C It depends on the value of i

D It is never computed

💡 Hint

Check execution_table row 2 under 'Expression 5 * 2 Computed?' column

At which iteration does the loop stop executing according to the execution_table?

A After iteration 2

B After iteration 4

C After iteration 3

D It never stops

💡 Hint

Look at the exit_note and the 'i' variable values in variable_tracker

If 'x = 5 * i' instead of 'x = 5 * 2', can 'x' be moved outside the loop?

A No, because x depends on i which changes each iteration

B Yes, because multiplication is fast

C Yes, but only for the first iteration

D No, because 5 * 2 is different

💡 Hint

Refer to key_moments about dependency on loop variable

Concept Snapshot

Loop optimization (invariant code motion):
- Find code inside loops that does not change each iteration.
- Move that code outside the loop to run once.
- This reduces repeated work and speeds up execution.
- Only safe if code does not depend on loop variables.
- Output remains the same after optimization.

Full Transcript

Loop optimization by invariant code motion means moving calculations or code inside a loop that do not change during the loop outside it. For example, in a loop running three times, if a calculation like 5 times 2 is done inside each iteration, it can be moved before the loop to run once. This saves time because the calculation is constant. The execution table shows that before optimization, the expression is computed every iteration, but after optimization, it is computed once and reused. Variables like 'i' change each iteration, but 'x' remains constant after moving outside. This optimization does not change the output but makes the loop faster. If the code depends on the loop variable, it cannot be moved outside safely.

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