Loop optimization (invariant code motion) in Compiler Design - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to identify the loop-invariant statement.

Compiler Design

for i in range(n):
    x = [1]
    y = i * 2

Drag options to blanks, or click blank then click option'

Aa + b

Bi + 1

Ci * 2

Di - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing expressions that depend on the loop variable as invariant.

Confusing loop-invariant with constant values.

The expression a + b does not depend on the loop variable i, so it is loop-invariant.

2fill in blank

medium

Complete the code to move the loop-invariant computation outside the loop.

Compiler Design

result = []
[1] = a + b
for i in range(n):
    result.append([1] * i)

Drag options to blanks, or click blank then click option'

Atemp

Bi

Cresult

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Placing the assignment inside the loop.

Using the loop variable as the temporary variable name.

Assigning a + b to a variable like temp outside the loop avoids recomputing it each iteration.

3fill in blank

hard

Fix the error in the code by correctly identifying the loop-invariant expression.

Compiler Design

for j in range(m):
    val = j * [1]
    process(val)

Drag options to blanks, or click blank then click option'

Am

Bk

Cval

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the loop variable j as invariant.

Confusing the loop limit m with invariant expressions.

The variable k is loop-invariant because it does not depend on j. Multiplying by k can be moved outside the loop.

4fill in blank

hard

Fill both blanks to optimize the loop by moving invariant code outside.

Compiler Design

[1] = q + r
for x in range(p):
    result = [2] * x
    print(result)

Drag options to blanks, or click blank then click option'

Atemp

Bq + r

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Not moving the assignment outside the loop.

Using the loop variable instead of the temporary variable.

Assigning q + r to temp outside the loop and using temp inside avoids repeated computation.

5fill in blank

hard

Fill all three blanks to correctly apply loop-invariant code motion.

Compiler Design

def compute(values):
    [1] = len(values)
    total = 0
    for i in range([2]):
        total += values[i] * [3]
    return total

Drag options to blanks, or click blank then click option'

An

Cfactor

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Calling len(values) inside the loop.

Using the loop variable as the multiplier.

Calculating len(values) once and storing it in n avoids repeated calls inside the loop. Multiplying by factor is invariant if factor does not change.

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