Question

In the context of code optimization, "Loop Invariant Code Motion" refers to:

• A. Removing loops that never execute.
• B. Moving computations that yield the same result regardless of the loop iteration outside the loop.
• C. Replacing expensive operations with cheaper ones inside a loop.
• D. Combining two loops into a single loop.

Hint:

To safely move a computation outside a loop, the compiler must ensure that the statement is not inside a conditional branch that might skip it, and that the variables involved are not modified anywhere within the loop body.

Answer 1

The Correct Option is B

Concept: Loop optimization is a set of compiler techniques aimed at reducing the execution time of repetitive code blocks.
• Loop Invariant: A computation whose result does not change as the loop progresses.
• Code Motion: Physically moving code from its original position to a more efficient one.

Step 1: Identifying invariant code.
Consider a loop where a calculation uses values that never change during the loop. For example, in {while (i < n) { x = y + z; i++; }}, $y+z$ is invariant.

Step 2: Applying the optimization.
The compiler moves the computation $x = y + z$ just before the loop header. Now, the calculation happens once instead of $n$ times.

Step 3: Distinguishing from other optimizations.
Option (C) describes "Strength Reduction." Option (D) describes "Loop Fusion." Only Option (B) accurately defines "Code Motion" of invariants.