Loop optimization (invariant code motion) in Compiler Design - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding loop-invariant code motion

Which of the following best describes the purpose of loop-invariant code motion in compiler optimization?

A Removing all loops from the program to simplify control flow.

B Duplicating loop body instructions to increase parallel execution.

C Moving calculations that do not change inside the loop to outside the loop to reduce repeated work.

D Changing the loop counter variable to a constant value.

💡 Hint

Think about what can be done to avoid repeating the same calculation multiple times inside a loop.

Loop-invariant code motion moves computations that produce the same result on every iteration outside the loop. This reduces the number of times the calculation is performed, improving efficiency.

📋 Factual

intermediate

Identifying loop-invariant statements

Consider the following loop:

for (int i = 0; i < n; i++) {
  int x = a + b;
  arr[i] = x * i;
}

Which statement is loop-invariant and can be moved outside the loop?

A arr[i] = x * i;

B int x = a + b;

C int i = 0;

D i < n

💡 Hint

Look for calculations that do not depend on the loop variable i.

The expression a + b does not depend on i and remains constant during the loop. So, int x = a + b; can be moved outside the loop.

🔍 Analysis

advanced

Effect of loop-invariant code motion on performance

Given a loop that executes 1,000,000 times, which of the following changes will most likely improve performance by applying loop-invariant code motion?

for (int i = 0; i < 1000000; i++) {
  int y = 5 * 10;
  process(y, i);
}

A Change the loop variable <code>i</code> to a floating-point number.

B Replace <code>process(y, i);</code> with <code>process(50, i);</code> inside the loop.

C Increase the loop count to 2,000,000 to utilize more CPU.

D Move <code>int y = 5 * 10;</code> outside the loop so it is computed once.

💡 Hint

Consider which calculation is repeated unnecessarily inside the loop.

Computing 5 * 10 inside the loop repeats the same calculation 1,000,000 times. Moving it outside the loop computes it once, reducing overhead and improving performance.

❓ Comparison

advanced

Comparing loop-invariant code motion with other optimizations

Which of the following statements correctly compares loop-invariant code motion with loop unrolling?

A Loop-invariant code motion moves constant computations outside the loop; loop unrolling duplicates the loop body to reduce loop overhead.

B Loop-invariant code motion duplicates the loop body; loop unrolling moves computations outside the loop.

C Both techniques remove loops entirely from the program.

D Loop unrolling moves invariant code outside the loop; loop-invariant code motion duplicates the loop body.

💡 Hint

Think about what each optimization tries to reduce: repeated calculations or loop control overhead.

Loop-invariant code motion reduces repeated calculations by moving them outside the loop. Loop unrolling reduces the overhead of loop control by repeating the loop body multiple times inside a single iteration.

❓ Reasoning

expert

Identifying safe loop-invariant code motion in nested loops

Consider the nested loops below:

for (int i = 0; i < n; i++) {
  for (int j = 0; j < m; j++) {
    int z = a + b;
    arr[i][j] = z * i * j;
  }
}

Which is the safest and most effective loop-invariant code motion to optimize this code?

A Move <code>int z = a + b;</code> outside both loops.

B Move <code>int z = a + b;</code> inside the inner loop only.

C Move <code>int z = a + b;</code> outside the outer loop only.

D Do not move <code>int z = a + b;</code> because it depends on <code>i</code> and <code>j</code>.

💡 Hint

Check if the expression depends on loop variables i or j.

The expression a + b does not depend on either i or j. Moving it outside both loops computes it once, saving repeated calculations in all iterations.

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