Loop optimizations: code motion, induction variables (brief, low weight)

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• When is an expression available at a point? from Lesson 6.5
• Why is a loop counter NAC at the loop header in constant propagation? from Lesson 6.3
• How do you recognise a loop in a flow graph? from Lesson 4.4

1 · The Story

📖

Laps

The printers set a long table of figures, one row per lap of the same instructions: “look up the column width, multiply the row number by 4, find that row’s figure, add it to the total, next row”.

Ishaan notices two wastes. The column width never changes between laps, so looking it up once before the first lap is enough. And “row number times 4” goes up by exactly 4 each lap, so instead of multiplying every time, he keeps a running offset and adds 4. In the end he does not even need the row number any more: he stops when the offset reaches the end.

2 · Predict First

🤔

In a loop with t1 = n * 4 (n unchanged in the loop) and t2 = 4 * i with i = i + 1 every iteration, how many multiplications per iteration remain after optimization? Write your guess down. The answer is in the vault.

3 · Core Concept

Loops and why they matter

Programs spend most of their time in inner loops. A loop in a flow graph has a header block that every path into the loop passes through, and a back edge from inside the loop to the header. A preheader is a new block inserted just before the header, to hold code moved out of the loop.

Code motion

A computation is loop-invariant if its operands are constants, are defined outside the loop, or are themselves loop-invariant. Code motion moves such a computation to the preheader, so it runs once. (Safety conditions, briefly: the moved statement must dominate the loop exits where its target is used, and there must be no other definition of the target in the loop.)

Induction variables and strength reduction

A basic induction variable changes by a constant each iteration: i = i + c. A derived induction variable is a linear function of it: j = a × i + b. Each time i increases by c, j increases by a × c, so j can be updated by addition instead of multiplication (strength reduction), initialised in the preheader.

Induction-variable elimination

If the basic induction variable i is used only to compute j and to test the loop condition, the test can be rewritten in terms of j (i ≤ n becomes j ≤ 4n), and i removed.

Other loop transformations (brief)

Loop unrolling repeats the body several times per iteration to reduce test-and-jump overhead. Loop jamming (fusion) merges two loops with the same range into one.

Story → compiler term

4 · Visual

Multiplications per iteration: 2 before, 0 after (counted). The last version tests t2 against t1 = 4n instead of i against n.

5 · Worked Examples

Example 1 Easy

Which statements in the loop of the first column are loop-invariant?

Solution

t1 = n * 4: n is not changed in the loop. The others depend on i, which changes every iteration. Ishaan’s “column width”.

Example 2 Medium

Apply strength reduction to t2 = 4 * i with i = i + 1.

Solution

t2 is a derived induction variable (a = 4, b = 0). Initialise t2 = 4 × (initial i) = 4 in the preheader and add t2 = t2 + 4 next to i = i + 1. The multiplication disappears from the loop (second column).

Example 3 GATE

After strength reduction, can i be eliminated? Give the new loop test.

Solution

i is now used only in the test i ≤ n. Since t2 = 4 × i, the test is equivalent to t2 ≤ 4n = t1 (which code motion already computes before the loop). Replace the test by if t2 <= t1 goto L and delete i (third column).

6 · Shortcuts

⚡

Loop-invariant test: every operand is a constant, defined only outside the loop, or itself invariant. Valid when: spotting candidates for code motion.

⚡

Derived induction variable j = a·i + b: replace by j = j + a·c each iteration, initialised before the loop. Valid when: strength reduction in loops.

7 · GATE Traps

⚠️

• A computation that uses a variable assigned anywhere in the loop is not invariant.
• Moved code goes to the preheader, not to an arbitrary earlier block.
• Strength reduction changes multiplication into addition, keeping the same values.
• Eliminating an induction variable requires rewriting the loop test.
• Loop optimizations have low GATE weight; recognise the terms and the simple transformations.

8 · Memory Hook

🧠

Hoist what never changes; step what changes steadily.

9 · Connect the Dots

Phase 6 is complete, and with it every syllabus topic. Phase 7 brings everything together: one sheet of all the rules, one program traced through every phase, mixed practice, and the final test.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markCode motion

Code motion moves a loop-invariant computation:

• (A) into the loop body
• (B) to the preheader before the loop
• (C) after the loop
• (D) into another function

Q2MCQ1 markInduction

In a loop with i = i + 2, the variable j = 3 * i + 1 is:

• (A) loop-invariant
• (B) a derived induction variable increasing by 6 per iteration
• (C) a basic induction variable
• (D) dead

Q3NAT1 markMultiplications

A loop computes t1 = n * 4 (n unchanged) and t2 = 4 * i (i += 1) every iteration. After code motion and strength reduction, how many multiplications remain inside the loop?

Numerical answer: ________

Q4MSQ1 markTerms

Which are loop optimizations?

• (A) code motion
• (B) strength reduction of induction variables
• (C) loop unrolling
• (D) computing FIRST sets

Q5MCQ1 markInvariant

Which statement inside a loop (where i changes each iteration and a, b never change) is loop-invariant?

• (A) x = i + a
• (B) y = a * b
• (C) z = y + i
• (D) w = a[i]

11 · Rule Card

• Loop: header + back edge; preheader holds moved code.
• Loop-invariant: operands constant, defined outside, or invariant; code motion → preheader.
• Basic induction variable: i = i + c; derived: j = a·i + b → j = j + a·c (strength reduction).
• Induction-variable elimination: rewrite the test in terms of j, delete i.
• Unrolling, jamming (fusion): brief.

12 · Concept Ledger

loop headerback edgepreheaderloop-invariant computationcode motionbasic induction variablederived induction variablestrength reduction in loopsinduction-variable eliminationloop unrolling / jamming

13 · Answer Vault