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.