CD Notes

Loop Optimization Techniques in Compiler Design

Complete guide to loop optimization covering loop invariant code motion, induction variables, strength reduction, loop unrolling, loop fusion, and other loop transformations.

Introduction

Loops dominate program execution time — a typical program spends 90% of its time in 10% of its code, mostly loops. Loop optimizations therefore have the highest payoff of any optimization category. Even small per-iteration savings multiply by millions of iterations.

Loop Detection (Natural Loops)

Dominators	Block A dominates block B if every path from entry to B goes through A.
Back edge: An edge B	A where A dominates B (loop back to header).
Natural loop of back edge B	A:
[B1]─	[B2]─→[B3]─┘ Back edge: B3→B1 (B1 dominates B3)
└──	[B4] B4 is after the loop (exit)

Loop Invariant Code Motion (LICM)

Move computations that produce the same result every iteration to before the loop:

Example

Before LICM: After LICM: i = 0 i = 0 while (i < n) { t = a * b ← hoisted! x = a * b ← invariant s = n - 1 ← hoisted! y = x + i while (i < n) { z = n - 1 ← invariant y = t + i i = i + 1 i = i + 1 } } Conditions for safe hoisting of "x = y OP z": 1. y and z are loop-invariant (defined outside or by other invariant) 2. x is not defined elsewhere in the loop 3. The statement dominates all loop exits where x is live 4. The statement dominates all uses of x in the loop Condition 3 ensures we don't execute code that might not execute: while (cond) { if (rare_condition) x = a / b // Can't hoist! b might be 0, and this } // might never execute in the loop.

Induction Variables

Basic induction variable	i = i + c (directly incremented)
Derived induction variable	j = a*i + b (linear function of basic IV)
j = 4 * i // derived	j = 4*i + 0
k = j + 100 // derived	k = 4*i + 100
i: incremented by 1 each iteration	basic IV
j: defined as 4*i	derived IV (coefficient=4, offset=0)
k: defined as j+100 = 4*i+100	derived IV (coefficient=4, offset=100)

Strength Reduction for Induction Variables

Replace multiplication with addition using recurrence:

Before strength reduction	After strength reduction:
Key insight	j goes 0, 4, 8, 12, ...
Each iteration	j_new = j_old + 4 (just addition!)

Induction Variable Elimination

After strength reduction, the original induction variable may be eliminable:

After strength reduction	After IV elimination:
Replace with	t1 < 4*n (test derived IV directly)
Now i is dead	eliminate it!
Saved	one ADD per iteration (for i++)

Loop Unrolling

Example

Replicate loop body to reduce overhead and enable optimization: Before (4 iterations): After (unrolled by 4): for (i=0; i<400; i++) { for (i=0; i<400; i+=4) { a[i] = a[i] + b[i]; a[i] = a[i] + b[i]; } a[i+1] = a[i+1] + b[i+1]; a[i+2] = a[i+2] + b[i+2]; a[i+3] = a[i+3] + b[i+3]; } Benefits: - Loop overhead reduced 4x (fewer comparisons, increments, branches) - Enables cross-iteration CSE and scheduling - Better instruction-level parallelism - Enables SIMD vectorization Costs: - Increased code size (4x for body) - May increase register pressure - Need cleanup loop for non-divisible trip counts

Loop Fusion and Fission

Loop Fusion (combining two loops)

Before: After fusion:

for (i=0; i<n; i++) for (i=0; i<n; i++) {

a[i] = b[i] + 1; a[i] = b[i] + 1;

for (i=0; i<n; i++) c[i] = a[i] * 2;

c[i] = a[i] * 2; }

// Two loops, a[i] in cache // One loop, better locality

// between loops → cold // a[i] used right after write

Loop Fission (splitting one loop)

Before: After fission:

for (i=0; i<n; i++) { for (i=0; i<n; i++)

a[i] = b[i] + 1; a[i] = b[i] + 1;

c[i] = d[i] * e[i]; for (i=0; i<n; i++)

} c[i] = d[i] * e[i];

// Many arrays, cache thrash // Each loop fits in cache better

Loop Interchange

Example

For nested loops, change iteration order for better cache access: Before (column-major access, poor cache): for (j = 0; j < N; j++) for (i = 0; i < N; i++) sum += A[i][j]; // stride = N (cache miss per access!) After interchange (row-major, good cache): for (i = 0; i < N; i++) for (j = 0; j < N; j++) sum += A[i][j]; // stride = 1 (sequential access, cache friendly) Condition: interchange is legal if there are no loop-carried dependencies that would be violated by the new order.

Interview Questions

Q: How does the compiler determine if an expression is loop-invariant?

A: An expression is loop-invariant if all its operands are: (1) defined outside the loop, (2) constants, or (3) themselves defined by loop-invariant expressions. The analysis iterates until a fixed point — marking invariant expressions may reveal that others depending on them are also invariant.

Q: When is loop invariant code motion unsafe?

A: When the hoisted code might not execute in the original (conditional inside the loop), might fault (division by zero, null dereference), or when the assigned variable is live on some path that doesn't execute the assignment. The compiler must verify dominance and exception safety before hoisting.

Q: What is the relationship between strength reduction and induction variable elimination?

A: Strength reduction converts multiplications (j=4*i) into additions (j+=4). This may make the original induction variable (i) unnecessary if it was only used for computing derived values and the loop test. IV elimination then removes i, replacing the loop test with a test on the derived variable.

Q: How much speedup does loop unrolling typically provide?

A: On modern architectures, 10-30% for compute-bound loops (reduced branch overhead, better scheduling). For memory-bound loops, less benefit since memory latency dominates. Excessive unrolling can hurt by causing instruction cache misses or increased register pressure.

Q: What determines the optimal unroll factor?

A: Factors include: number of available registers (don't spill), instruction cache size (unrolled body must fit), pipeline depth (enough instructions to hide latency), SIMD width (unroll to fill vector registers), and trip count distribution (must handle remainders).

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Loop Optimization Techniques in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, optimization, loop, loop optimization techniques in compiler design

Continue learning this concept

Code OptimizationIntroduction to Code Optimization in Compiler DesignComprehensive introduction to compiler code optimization covering optimization levels, classification, basic blocks, control flow graphs, and the role of optimization in the compilation pipeline.Code OptimizationCommon Subexpression Elimination (CSE) in Compiler OptimizationDetailed guide to common subexpression elimination covering local and global CSE, available expressions analysis, DAG-based detection, and practical optimization examples.Code OptimizationConstant Folding Optimization in Compiler DesignComplete guide to constant folding optimization covering compile-time evaluation, constant expressions, type handling, and interaction with other optimizations in the compilation pipeline.Code OptimizationConstant Propagation in Compiler OptimizationComplete guide to constant propagation optimization covering forward analysis, conditional constant propagation, lattice framework, and practical implementation with dataflow analysis.Code OptimizationDead Code Elimination in Compiler OptimizationComplete guide to dead code elimination covering unreachable code, useless computations, liveness analysis, and aggressive dead code elimination techniques in compiler optimization.Code OptimizationGlobal Optimization Techniques in Compiler DesignComprehensive guide to global (intraprocedural) optimization techniques including dataflow analysis frameworks, reaching definitions, live variables, and global optimization passes.

PreviousLocal Optimization Techniques in Compiler Design NextPeephole Optimization in Compiler Design

CD Notes

Loop Optimization Techniques in Compiler Design

Complete guide to loop optimization covering loop invariant code motion, induction variables, strength reduction, loop unrolling, loop fusion, and other loop transformations.

Introduction

Loop Detection (Natural Loops)

Dominators	Block A dominates block B if every path from entry to B goes through A.
Back edge: An edge B	A where A dominates B (loop back to header).
Natural loop of back edge B	A:
[B1]─	[B2]─→[B3]─┘ Back edge: B3→B1 (B1 dominates B3)
└──	[B4] B4 is after the loop (exit)

Loop Invariant Code Motion (LICM)

Move computations that produce the same result every iteration to before the loop:

Example

Induction Variables

Basic induction variable	i = i + c (directly incremented)
Derived induction variable	j = a*i + b (linear function of basic IV)
j = 4 * i // derived	j = 4*i + 0
k = j + 100 // derived	k = 4*i + 100
i: incremented by 1 each iteration	basic IV
j: defined as 4*i	derived IV (coefficient=4, offset=0)
k: defined as j+100 = 4*i+100	derived IV (coefficient=4, offset=100)

Strength Reduction for Induction Variables

Replace multiplication with addition using recurrence:

Before strength reduction	After strength reduction:
Key insight	j goes 0, 4, 8, 12, ...
Each iteration	j_new = j_old + 4 (just addition!)

Induction Variable Elimination

After strength reduction, the original induction variable may be eliminable:

After strength reduction	After IV elimination:
Replace with	t1 < 4*n (test derived IV directly)
Now i is dead	eliminate it!
Saved	one ADD per iteration (for i++)

Loop Unrolling

Example

Loop Fusion and Fission

Loop Fusion (combining two loops)

Before: After fusion:

for (i=0; i<n; i++) for (i=0; i<n; i++) {

a[i] = b[i] + 1; a[i] = b[i] + 1;

for (i=0; i<n; i++) c[i] = a[i] * 2;

c[i] = a[i] * 2; }

// Two loops, a[i] in cache // One loop, better locality

// between loops → cold // a[i] used right after write

Loop Fission (splitting one loop)

Before: After fission:

for (i=0; i<n; i++) { for (i=0; i<n; i++)

a[i] = b[i] + 1; a[i] = b[i] + 1;

c[i] = d[i] * e[i]; for (i=0; i<n; i++)

} c[i] = d[i] * e[i];

// Many arrays, cache thrash // Each loop fits in cache better

Loop Interchange

Example

Interview Questions

Q: How does the compiler determine if an expression is loop-invariant?

Q: When is loop invariant code motion unsafe?

Q: What is the relationship between strength reduction and induction variable elimination?

Q: How much speedup does loop unrolling typically provide?

Q: What determines the optimal unroll factor?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Loop Optimization Techniques in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, optimization, loop, loop optimization techniques in compiler design

Continue learning this concept

PreviousLocal Optimization Techniques in Compiler Design NextPeephole Optimization in Compiler Design