LI.6.6 Loop optimizations · GATE 2027 Compiler Design

ACompressed recap

🧾

Loops have a header entered by every path and a back edge. Code motion moves loop-invariant computations to a preheader. Induction variables change by fixed amounts; derived ones (j = a·i + b) are updated by addition instead of multiplication (strength reduction), and the basic variable can then often be eliminated by rewriting the test. Unrolling and jamming are further, briefly examined transformations.

BMerged rule card

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

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.

CInterleaved GATE-style questions

Q1MCQ1 markInvariant

A computation is loop-invariant if:

(A) it is inside the loop
(B) its operands do not change during the loop
(C) it uses the loop counter
(D) it is the loop test

Q2NAT1 markStep

With i = i + 3 per iteration, by how much does j = 5 * i − 2 change per iteration?

Numerical answer: ________

Q3MCQ1 markPreheader

The preheader is:

(A) the first block inside the loop body
(B) a block inserted just before the loop header
(C) the exit block
(D) the back edge

Q4MCQ2 marksElimination

After strength reduction makes t = 4 * i an additive variable, the test i n can become:

(A) t n
(B) t 4 * n
(C) i t
(D) t i

Q5MSQ1 markTerms

Which describe loop unrolling?

(A) repeat the body several times per iteration
(B) reduce the number of loop tests and jumps
(C) merge two loops into one
(D) move invariant code out

Q6MCQ1 markBasic

Which is a basic induction variable?

(A) i = i + 4
(B) j = 3 * i
(C) k = a[i]
(D) m = n * 2

Q7MCQ1 markSafety

Moving x = a * b out of a loop is unsafe if:

(A) a and b are constants
(B) x is assigned elsewhere in the loop too
(C) the loop runs many times
(D) a * b is cheap

Q8NAT2 marksCount

A loop runs 100 times and contains one loop-invariant multiplication. How many multiplications are executed in total before and after code motion (enter the difference)?

Numerical answer: ________

Answer Vault

Try the questions first. Open when you are ready to check.

Q1 Answer: (B)1 mark

Then its value is the same every iteration.

(A) is wrong: All loop code is inside.
(C) is wrong: The counter changes.
(D) is wrong: The test usually uses the counter.