Loop Optimization
1. Why Loops First
Programs spend 90% time in 10% code (loops) — loop wins dominate. Operates on natural loops (header + back edge + body).
2. Techniques (exam list — 4 core)
| Opt | What | Example |
|---|---|---|
| Code motion (hoisting) | move invariant out to preheader | for i: x=a+b (a,b fixed) → before loop |
| Induction-var elim | replace i*stride with incrementing temp |
t=t+4 instead of i*4 per iter |
| Strength reduction | expensive → cheap in loop | x*2 → x+x or shift inside loop |
| Unrolling / fusion | duplicate body / merge loops | for 4 iters → 1 iter doing 4 (fewer branches, more ILP) |
3. Worked — motion + reduction
for i=0..n: a[i] = b + i*4
→ t0 = b (hoist, invariant)
→ t1 = 0; for i: a[i]=t0+t1; t1+=4 (no multiply per iter)
Safety: hoisted stmt must dominate exits and operands invariant (reaching-defs outside loop).
4. Other LoopOpts
Unswitching (if invariant → two loop versions), tiling for cache (see Module 5), parallelization if no carried dependence.
5. Exam Points
- List 4 loop opts with examples — 7-10 marks, most frequent opt question.
- Hoist invariant / elim induction var on given loop — 7 marks, frequent.
- Safety conditions for motion — 3-5 marks, frequent.