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.