Compiler Optimizations

Naive codegen is slow. Optimizations make compiled code faster (sometimes much faster).

Constant folding: 2 + 3 → 5 at compile time.

Constant propagation: x = 5; y = x + 1; → y = 6;.

Dead code elimination: remove unreachable code, unused vars.

Common subexpression elimination: a*b + a*b → compute a*b once.

Loop unrolling: for i in 1..4: x[i]=0 → x[1]=0; x[2]=0; x[3]=0; x[4]=0.

Strength reduction: i*2 → i << 1.

Inlining: replace call with body. Cost: code size. Benefit: avoid call overhead + enables further optimization.

Tail call optimization: if last action is a call, reuse current frame. Crucial for functional languages, optional for C.

Register allocation: assign IR temps to registers (graph coloring).

Loop invariant code motion: hoist invariant expressions out of loops.

Vectorization: for i: x[i] = a[i] + b[i] → SIMD addps xmm0, xmm1.

LLVM has 100+ optimization passes. Can be applied in order; some interact.

int sum_squares(int n) {
    int total = 0;
    for (int i = 0; i < n; i++) {
        total += i * i;
    }
    return total;
}

-O3 with LLVM:

• Vectorization: process 4-8 i's per iteration.
• Loop unrolling.
• Algebraic simplification: closed-form for sum of squares.

Result: n^3 / 3 + n^2 / 2 + n / 6 directly. From O(n) to O(1)!

Compilers prove safety: vectorization assumes no aliasing; loop opts assume no exceptions.

Trade-off: aggressive opts = harder debugging (vars optimized away). -Og for "optimized for debugging".

Costs: compile time. -O0 fast compile + slow code. -O3 slow compile + fast code.