COMPILER DESIGN / 5. OPTIMIZATION
Compiler Optimization
Making code faster and smaller — the techniques that make compiled code beat handwritten code
EXPLANATION
Optimization transforms the IR into faster or smaller code, without changing the program's meaning (observable behavior). Modern compilers perform hundreds of optimization passes. This is why optimized compiled C can be faster than hand-written assembly — humans can't track all the interactions between optimizations. Key principle: correctness first. An optimization that changes behavior (even to make it "faster") is a BUG in the compiler. LOCAL OPTIMIZATIONS (within a basic block): Constant Folding: Evaluate constant expressions at compile time. "x = 2 + 3" → "x = 5" (no runtime addition needed) "y = 60 * 60 * 24" → "y = 86400" Constant Propagation: Replace variable uses with their known constant values. "x = 5; y = x + 3" → "x = 5; y = 8" Algebraic Simplification: Use algebraic identities to simplify expressions. "x * 1" → "x" "x + 0" → "x" "x * 2" → "x << 1" (shift is faster than multiply) "x * 0" → "0" Dead Code Elimination (DCE): Remove code whose results are never used. "t = x + y; return x" → "return x" (t is dead — never used after) Unreachable code after return/goto. Common Subexpression Elimination (CSE): Don't compute the same expression twice. "a = b+c; d = b+c" → "t=b+c; a=t; d=t" GLOBAL OPTIMIZATIONS (across basic blocks): Loop Optimizations (most impactful — loops run many times): - Loop Invariant Code Motion (LICM): move computations that don't change inside the loop to before the loop. "for i in range(n): x = a+b; arr[i] = x*i" → hoist "a+b" out of loop. - Loop Unrolling: execute loop body 2, 4, 8 times per iteration. Reduces loop overhead, enables more instruction-level parallelism. - Loop Fusion: combine two loops over same range into one. Better cache behavior. - Strength Reduction: replace expensive operations in loops. "i*4" → accumulate "+4" each iteration instead of multiply. Inlining: Replace function call with function body. Eliminates call overhead, enables further optimization across the call boundary. Too much inlining = code bloat. Tail Call Optimization (TCO): A recursive call in tail position (last thing function does) is transformed into a loop. Prevents stack overflow for recursive programs. Register Allocation: Assign IR temporaries to physical CPU registers. Variables used together compete for registers. Spilled variables go to memory (stack). Graph coloring algorithm: variables that are "live" at the same time can't share a register (adjacent in interference graph). Instruction Scheduling: Reorder instructions to avoid pipeline stalls (data hazards). Don't put dependent instructions adjacent — insert independent instructions between them to let the pipeline fill.
DIAGRAM
OPTIMIZATION PIPELINE:
Original TAC: After constant folding + propagation:
x = 2 x = 2
y = 3 y = 3
t1 = x + y t1 = 5 ← 2+3 computed at compile time
t2 = t1 * 1 t2 = 5 ← *1 eliminated
t3 = t2 + 0 t3 = 5 ← +0 eliminated
result = t3 result = 5 ← all propagated
After dead code elimination:
result = 5 ← x, y, t1, t2, t3 never used again
LOOP INVARIANT CODE MOTION:
Before: After:
for i in range(n): c = a + b ← hoisted out!
c = a + b for i in range(n):
arr[i] = c * i arr[i] = c * i
COMMON SUBEXPRESSION ELIMINATION:
Before: After:
a = x*y + z t = x*y ← computed once
b = x*y - z a = t + z
b = t - z
INLINING:
def square(x): return x*x
y = square(5) y = 5*5 = 25 ← inlined + foldedCODE