Optimization

Before any optimization can happen, the compiler must understand the structure of the program. A basic block is a maximal sequence of straight-line code with exactly one entry point (the first instruction) and one exit point (the last instruction, which is a branch or return). No jumps land in the middle; no branches occur until the end. Within a basic block, instructions execute sequentially and unconditionally — which makes local analysis tractable.

A control-flow graph (CFG) is a directed graph where nodes are basic blocks and edges represent possible control flow. An edge from block A to block B exists if execution can proceed from the last instruction of A to the first instruction of B. Every function has a distinguished entry block and one or more exit blocks.

The CFG is the fundamental data structure for almost all global optimization. Dataflow analyses, dominator trees, loop detection — all of it lives on the CFG. Building the CFG is the first step after generating three-address code (or IR like LLVM IR).

Analogy: Think of a basic block as a stretch of highway between intersections. Within that stretch you drive straight. The CFG is the road map of the entire city — it tells you which stretches connect to which.

# Source
def foo(x):
    if x > 0:
        y = x * 2
    else:
        y = -x
    return y

# Basic blocks in the CFG:
# BB1: (entry) t1 = x > 0; if t1 goto BB2 else BB3
# BB2:         y = x * 2; goto BB4
# BB3:         y = -x;    goto BB4
# BB4: (exit)  return y

# Edges: BB1->BB2, BB1->BB3, BB2->BB4, BB3->BB4

Block A dominates block B (written A dom B) if every path from the entry block to B passes through A. Dominance is the key structural property behind loop detection and many transformations.

The immediate dominator of B (idom(B)) is the closest strict dominator — the last block every path must pass through before reaching B. These immediate-dominator relationships form a tree: the dominator tree. The entry block is the root; every other block has exactly one parent.

Why does this matter? Dominators tell you what is always computed before a given point. If block A dominates block B, any computation done in A is guaranteed to have happened before B executes. This is precisely the safety condition for placing hoisted code: you can move a computation to A only if A dominates all uses of that computation.

Dominators are computed efficiently with the Lengauer-Tarjan algorithm (O(n α(n)) on the CFG). In practice, a simple iterative dataflow algorithm converges quickly on CFGs encountered in real programs.

Key property: The dominator tree is central to SSA (Static Single Assignment) form construction. The dominance frontier of a block B is the set of blocks where B's dominance ends — exactly where φ-functions must be placed in SSA.

# Iterative dominator computation
# dom[n] = set of all dominators of n

def compute_dominators(blocks, entry, predecessors):
    dom = {entry: {entry}}
    for b in blocks:
        if b != entry:
            dom[b] = set(blocks)  # pessimistic start
    changed = True
    while changed:
        changed = False
        for b in blocks:
            if b == entry:
                continue
            new_dom = None
            for p in predecessors[b]:
                if p in dom:
                    s = dom[p] | {b}
                    new_dom = s if new_dom is None else new_dom & s
            if new_dom and new_dom != dom.get(b):
                dom[b] = new_dom
                changed = True
    return dom

Dataflow analysis is the formal foundation for almost every global optimization. The idea is to compute, at each program point, some abstract property of the program state — which variables are live, which expressions are available, which values are constant. These properties are computed by propagating information along the CFG edges until a fixed point is reached.

The framework rests on lattice theory. A lattice is a partially ordered set where every pair of elements has a least upper bound (join, ⊔) and a greatest lower bound (meet, ⊓). For each analysis:

• The lattice describes the space of possible abstract values (e.g., {⊤, constant c, ⊥} for constant propagation)
• Each basic block has a transfer function f_B that maps the incoming abstract state to the outgoing abstract state
• Dataflow equations are solved by iterative fixed-point computation, starting from an initial state and applying transfer functions until nothing changes

Forward analyses propagate information from predecessors to successors (e.g., reaching definitions, available expressions). Backward analyses propagate from successors to predecessors (e.g., liveness).

The fundamental theorem: If transfer functions are monotone (order-preserving) and the lattice has finite height, the iterative algorithm terminates at the least fixed point (most precise safe answer).

For forward analysis:

OUT[B] = f_B(IN[B])
IN[B]  = ⊓ { OUT[P] : P is a predecessor of B }

For backward analysis:

IN[B]  = f_B(OUT[B])
OUT[B] = ⊓ { IN[S] : S is a successor of B }

The beauty here is that the same algorithmic skeleton — initialize, iterate to fixed point — handles a dozen different analyses simply by changing the lattice and transfer functions.

# Generic worklist-based dataflow solver
from collections import deque

def dataflow(blocks, entry, successors, transfer_fn,
             meet, top, forward=True):
    out = {b: top for b in blocks}
    out[entry] = transfer_fn(entry, top)
    worklist = deque(blocks)
    while worklist:
        b = worklist.popleft()
        neighbors = successors[b] if forward else predecessors[b]
        in_val = meet(out[p] for p in neighbors) if neighbors else top
        new_out = transfer_fn(b, in_val)
        if new_out != out[b]:
            out[b] = new_out
            worklist.extend(neighbors)
    return out

Constant folding is the simplest optimization: evaluate constant expressions at compile time. If the compiler sees x = 2 + 3, it replaces it with x = 5. No runtime addition needed. This is a purely local transformation that the parser or IR builder can apply immediately.

Constant propagation is the global version. It uses dataflow analysis to track which variables hold constant values at each program point. The lattice for each variable is: ⊤ (unknown/not yet seen), a specific constant value c, or ⊥ (definitely not constant — the variable takes multiple values). The meet operation is: c ⊓ c = c; c ⊓ d = ⊥ (c ≠ d); ⊤ ⊓ x = x.

The transfer function for an assignment x = e: evaluate e under the current constant map. If e evaluates to a constant c, set x's value to c; otherwise set it to ⊥.

Sparse Conditional Constant Propagation (SCCP) (Wegman & Zadeck 1991) is the state-of-the-art algorithm. It simultaneously propagates constants AND tracks which branches are reachable. If a branch condition evaluates to a known constant, the false branch is marked unreachable and ignored. This allows constants to propagate across branches that naive constant propagation would conservatively block.

Example: After constant propagation, dead branches and their code become visible to dead code elimination — the two passes compose powerfully.

# Constant propagation lattice and transfer function

TOP = 'top'   # not yet analyzed
BOT = 'bot'   # not a constant

def meet(a, b):
    if a == TOP: return b
    if b == TOP: return a
    if a == b:   return a
    return BOT

def eval_expr(expr, env):
    """Try to reduce expr to a constant under env."""
    if isinstance(expr, int): return expr
    if isinstance(expr, str):   # variable
        v = env.get(expr, TOP)
        return v if isinstance(v, int) else None
    op, l, r = expr
    lv, rv = eval_expr(l, env), eval_expr(r, env)
    if isinstance(lv, int) and isinstance(rv, int):
        return {'+': lv+rv, '-': lv-rv,
                '*': lv*rv, '/': lv//rv}[op]
    return None

def transfer(block_stmts, in_env):
    env = dict(in_env)
    for lhs, rhs in block_stmts:
        val = eval_expr(rhs, env)
        env[lhs] = val if val is not None else BOT
    return env

A statement x = expr is dead if x is never used after this point. Executing it wastes time and space. Dead code elimination (DCE) removes such statements.

The formal prerequisite is liveness analysis: a backward dataflow analysis that computes, for each program point, the set of variables that are live — that is, their current value may be used along some future execution path.

The equations:

IN[B]  = USE[B]  ∪  (OUT[B] − DEF[B])
OUT[B] = ∪ { IN[S] : S is a successor of B }

Here USE[B] = variables used in B before being defined; DEF[B] = variables defined in B before being used. The meet operation is set union (we take the pessimistic view: a variable is live if any successor needs it).

Once liveness is known, DCE is trivial: for each assignment x = expr, if x is not in the live-out set of that instruction, and x is not an output variable or has side effects, the assignment is dead and can be deleted. Re-run until no changes.

Aggressiveness: Simple DCE handles assignments. More aggressive variants (like LLVM's aggressive DCE / mark-sweep DCE) reason about what is truly necessary — starting from "necessary" instructions (returns, stores, calls with side effects) and mark anything that feeds a necessary instruction as necessary; everything else is dead.

Caveat: Side effects must be respected. x = foo() cannot be eliminated if foo has observable side effects, even if x is never read.

# Backward liveness analysis

def liveness(blocks, successors, use, defn):
    """use[b], defn[b] are sets of variables."""
    live_in  = {b: set() for b in blocks}
    live_out = {b: set() for b in blocks}
    changed = True
    while changed:
        changed = False
        for b in reversed(blocks):  # process in reverse post-order
            new_out = set()
            for s in successors[b]:
                new_out |= live_in[s]
            new_in = use[b] | (new_out - defn[b])
            if new_in != live_in[b] or new_out != live_out[b]:
                live_in[b]  = new_in
                live_out[b] = new_out
                changed = True
    return live_in, live_out

def dce(instructions, live_out_per_instr):
    result = []
    for instr in instructions:
        lhs, rhs, has_side_effect = instr
        if has_side_effect or lhs in live_out_per_instr[instr]:
            result.append(instr)
        # else: drop dead assignment
    return result

If the compiler computes a * b + c in block 1, and the same expression appears unchanged in block 3 (with no intervening modification of a, b, or c), there is no need to recompute it. Common Subexpression Elimination (CSE) detects these redundancies and replaces later occurrences with a reference to a temporary that holds the already-computed value.

The formal underpinning is available expressions analysis: a forward dataflow analysis that computes, at each program point, the set of expressions whose current value has already been computed and not invalidated.

An expression e is available at program point p if:

1. On every path from entry to p, e has been computed at least once.
2. None of the variables in e have been modified since the last computation.

The equations (using must-be-available, so meet = intersection):

OUT[B] = (IN[B] − KILL[B]) ∪ GEN[B]
IN[B]  = ∩ { OUT[P] : P is a predecessor of B }

GEN[B] = expressions computed in B whose operands are not subsequently modified in B. KILL[B] = expressions that contain a variable defined in B.

Initialize IN[entry] = ∅; IN[all others] = {all expressions} (optimistic start — intersection-based analysis needs this).

Local CSE works within a single basic block using a simple hash table (value numbering). Global CSE uses the available expressions dataflow. Value numbering in SSA form is even more elegant: two expressions with the same operation and same value-numbered operands always produce the same result, by construction.

# Local value numbering (within one basic block)
# Map expression -> canonical temp name

def local_value_number(instructions):
    val_num = {}   # var -> value_id
    expr_to_id = {} # (op, id1, id2) -> value_id
    rewrite = {}   # var -> canonical var
    next_id = [0]
    result = []

    def new_id():
        next_id[0] += 1
        return next_id[0]

    for (lhs, op, r1, r2) in instructions:
        v1 = val_num.get(r1, new_id())
        val_num.setdefault(r1, v1)
        v2 = val_num.get(r2, new_id())
        val_num.setdefault(r2, v2)
        key = (op, min(v1,v2), max(v1,v2))  # commutative
        if key in expr_to_id:
            # CSE: reuse existing temp
            val_num[lhs] = expr_to_id[key]
            rewrite[lhs] = [t for t,v in val_num.items()
                            if v == expr_to_id[key]][0]
        else:
            vid = new_id()
            expr_to_id[key] = vid
            val_num[lhs] = vid
            result.append((lhs, op, r1, r2))
    return result

Loops are the hot spots of most programs. A computation inside a loop that executes a million times, but whose result doesn't change across iterations, should be computed once before the loop. This is Loop-Invariant Code Motion (LICM).

LICM: An expression inside a loop is loop-invariant if all its operands are defined outside the loop, or are themselves loop-invariant. Such expressions can be hoisted to the loop preheader — a block that is inserted immediately before the loop header and that dominates all blocks in the loop. Condition for safe hoisting: the block containing the expression must dominate all loop exits (otherwise the expression might not execute on the original path, and it could have side effects or could fault).

Strength Reduction: Replace expensive operations with cheaper equivalent ones. The classic case is replacing a multiplication inside a loop with an addition. If i is the loop induction variable and you compute i * 4 in the body, replace it with a new variable j initialized to 0 * 4 = 0 before the loop, incremented by 4 each iteration, and substitute j for i * 4.

Induction Variable Elimination: After strength reduction, the original induction variable i may only be used in the loop test. If j encodes the same information, i can be eliminated and the test rewritten in terms of j.

Loop Unrolling: Replicate the loop body 2x, 4x, or 8x, updating the induction variable by 2, 4, or 8 each iteration. Benefits: fewer branch/test instructions, more opportunities for instruction-level parallelism and vectorization, reduced loop overhead. Cost: larger code size (instruction cache pressure). Modern compilers (GCC -O3, LLVM with -unroll-count) choose the unroll factor based on the loop body size and target micro-architecture.

// Before LICM and strength reduction
for (int i = 0; i < n; i++) {
    a[i] = b[i] * stride + base;  // stride, base loop-invariant
}

// After LICM: hoist loop-invariant 'base' (already trivial here)
// After strength reduction on 'b[i] * stride':
int j = b[0] * stride;   // or use pointer walk
for (int i = 0; i < n; i++) {
    a[i] = b[i] * stride + base;  // stride-reduce b pointer walk
}

// Strength reduction on array indexing:
// b[i] = *(b + i*sizeof(int)) -- replace i*4 with additive update
int *bp = b, *ap = a;
for (int i = 0; i < n; i++, bp++, ap++) {
    *ap = *bp * stride + base;
}

// Loop unrolling (factor 4):
for (int i = 0; i < n-3; i += 4) {
    a[i]   = b[i]   * stride + base;
    a[i+1] = b[i+1] * stride + base;
    a[i+2] = b[i+2] * stride + base;
    a[i+3] = b[i+3] * stride + base;
}
// cleanup loop for remaining elements

Peephole optimization works on a small sliding window (the "peephole") over the instruction stream, replacing inefficient patterns with better equivalents. It is typically applied to the final machine code or near-final IR, after all higher-level optimizations. Despite its simplicity, it can yield significant gains because code generators are often naive about local patterns.

Classic peephole rules:

• x = x + 0 → eliminate
• x = x * 1 → eliminate
• x = x * 2 → x = x << 1
• LOAD r, mem; STORE mem, r immediately following → eliminate the store (value already in memory)
• JUMP L; L: → eliminate the jump (falls through)
• MOV r1, r2; MOV r2, r1 → eliminate the second move
• x = -(-x) → x = x
• if (x != 0) goto L; goto M; L: → if (x == 0) goto M

Peephole optimizers are often implemented as rewriting systems: a set of pattern → replacement rules applied exhaustively until no rule fires. LLVM's InstCombine pass is the most sophisticated such pass in production compilers — it contains hundreds of algebraic identities and runs on LLVM IR before code generation.

Peephole optimization is also used in JIT compilers (like V8 and HotSpot) because it is cheap to apply at runtime and can fix inefficiencies introduced by fast, non-optimizing code generation paths.

# Peephole optimizer (on a tiny IR)
# Instructions: (op, dest, src1, src2)

def peephole(instrs):
    changed = True
    while changed:
        changed = False
        result = []
        i = 0
        while i < len(instrs):
            instr = instrs[i]
            op, dst, s1, s2 = instr

            # x = x + 0  or  x = 0 + x  →  eliminate
            if op == 'ADD' and (s2 == 0 or s1 == 0):
                src = s1 if s2 == 0 else s2
                result.append(('MOV', dst, src, None))
                changed = True

            # x = x * 1 → eliminate
            elif op == 'MUL' and (s2 == 1 or s1 == 1):
                src = s1 if s2 == 1 else s2
                result.append(('MOV', dst, src, None))
                changed = True

            # x = y * 2 → x = y << 1
            elif op == 'MUL' and s2 == 2:
                result.append(('SHL', dst, s1, 1))
                changed = True

            # LOAD r m; STORE m r → keep LOAD, drop STORE
            elif (op == 'LOAD' and i+1 < len(instrs)
                  and instrs[i+1] == ('STORE', s1, dst, None)):
                result.append(instr)
                i += 2  # skip the redundant STORE
                changed = True
                continue

            else:
                result.append(instr)
            i += 1
        instrs = result
    return instrs

Inlining replaces a function call site with a copy of the called function's body, with actual arguments substituted for formal parameters. This eliminates call overhead (stack frame setup, register saving, branch), enables all the other optimizations to work across the call boundary, and exposes specialization opportunities (if arguments are constants, constant propagation can simplify the inlined body dramatically).

Inlining is one of the highest-leverage optimizations because function calls are barriers to most analyses. Once a function is inlined, the caller's optimizer can see the callee's code and apply CSE, DCE, constant propagation, and loop optimizations across the combined body.

When to inline: The decision is a cost-benefit tradeoff. Benefits are clear — no call overhead, more optimization opportunities. Costs: code size growth (bad for instruction cache), longer compilation times, possible register pressure increases. Compilers use heuristics: inline if the callee is small (< ~30 instructions), if the call site is in a hot loop (detected by profiling), or if it's a static inline / __forceinline annotation.

Inlining hazards:

• Recursive functions cannot be fully inlined (inlining up to a depth is possible but rarely worth it)
• Indirect calls (virtual dispatch, function pointers) require devirtualization before inlining
• Code size explosion: inlining a function called at 50 sites creates 50 copies

Profile-guided optimization (PGO) solves the call-site heat problem: instrument the program, gather profiles from representative runs, then inline only hot call sites. GCC and LLVM both support PGO; it reliably gives 10-30% speedups on real applications.

Interprocedural constant propagation: When a function is called with a known constant argument, an inlined (or cloned) version can be specialized. This is how compilers optimize generic code paths.

// Before inlining
static inline int square(int x) { return x * x; }

int sum_of_squares(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++)
        s += square(i);   // call here
    return s;
}

// After inlining square:
int sum_of_squares(int n) {
    int s = 0;
    for (int i = 1; i <= n; i++)
        s += i * i;   // no call; body substituted
    return s;
}
// Now the loop body is exposed to strength reduction,
// vectorization, and other loop transforms.

Static Single Assignment (SSA) form is an IR property where every variable is defined exactly once, and every use refers to a unique definition. When a variable in the original program is assigned in multiple places, each assignment gets a fresh name (x → x₁, x₂, x₃, ...). At control-flow merge points where different definitions of the same original variable join, a special φ-function (phi-function) is inserted: x₃ = φ(x₁, x₂) means x₃ takes the value of x₁ if control came from the left predecessor, x₂ if from the right.

SSA was introduced by Cytron, Ferrante, Rosen, Wegman, and Zadeck (1991) and is now the standard IR for all major optimizing compilers (LLVM IR, GCC's GIMPLE, V8's Turbofan, the JVM JIT).

Why SSA makes optimization easier:

• Use-def chains are trivial: Every use has exactly one definition. No need to compute reaching definitions — it's encoded in the name.
• CSE becomes syntactic: Two expressions with the same operator and same SSA variable names always compute the same value.
• Sparse analyses: Data flows along def-use edges directly, not through every instruction. Constant propagation in SSA is O(N) instead of O(N²).
• Dead code is syntactic: A definition with no uses is dead. No liveness analysis needed for basic DCE.

Constructing SSA: Place φ-functions at dominance frontiers (where a block's dominance ends — precisely where different definitions of a variable can merge). Then rename variables in a DFS over the dominator tree.

Out of SSA: Before code generation, φ-functions are removed by inserting parallel copies on each incoming CFG edge — a process called SSA deconstruction or out-of-SSA translation.

# Original (x assigned twice)
x = 1
if cond:
    x = 2
return x

# In SSA form:
x1 = 1
if cond goto BB2 else BB3
# BB2:
x2 = 2
goto BB4
# BB3:
# (x1 still holds here)
goto BB4
# BB4:
x3 = phi(x2, x1)  # x3 = x2 if from BB2, x1 if from BB3
return x3

# Now constant propagation is trivial:
# x1=1 (constant), x2=2 (constant)
# If cond is known, phi resolves to a constant too.
# If cond unknown: x3 = phi(2, 1) -- not constant (BOT)

The optimizations above mostly assume scalar variables. But real programs use pointers and arrays, and this introduces aliasing: two different expressions may refer to the same memory location. If p and q might alias (point to the same location), then storing through p kills information about q, limiting CSE, LICM, and other passes.

Alias analysis determines, for each pair of memory accesses (pointer dereferences, array accesses), whether they must alias (always the same location), may alias (sometimes), or cannot alias (definitely different). More precise alias information → more aggressive optimization.

Points-to analysis (e.g., Andersen's analysis, Steensgaard's analysis) computes for each pointer variable the set of locations it might point to. Andersen's is flow-insensitive, context-insensitive, and runs in O(n³) but is widely used. Steensgaard's is O(n α(n)) but less precise.

Type-based alias analysis (TBAA): In C, the strict aliasing rule says a pointer of type int* cannot alias a pointer of type float* (with some exceptions). GCC and LLVM exploit this: -O2 enables strict aliasing, allowing the compiler to assume float* p and int* q are independent. This enables hoisting stores and CSE across pointer writes. (This is why writing to float* through a reinterpreted int* is undefined behavior in C — the compiler may silently produce wrong code.)

Memory SSA: LLVM and GCC represent memory state in SSA form using virtual memory operands, allowing the full power of SSA-based analyses (reaching definitions, dead store elimination, load-store forwarding) to apply to memory as well as scalar variables.

// C: strict aliasing
void copy(float *dst, const int *src, int n) {
    for (int i = 0; i < n; i++)
        dst[i] = src[i];  // float* and int* cannot alias
}
// Compiler can freely vectorize — no aliasing concern.

// Without restrict, these might alias:
void add(int *a, const int *b, const int *c, int n) {
    for (int i = 0; i < n; i++)
        a[i] = b[i] + c[i]; // a and b might alias!
}
// With restrict (C99): compiler can assume no aliasing:
void add_r(int *restrict a, const int *restrict b,
           const int *restrict c, int n) {
    for (int i = 0; i < n; i++)
        a[i] = b[i] + c[i];
}

A production compiler does not apply one optimization — it applies dozens in a carefully ordered pipeline of passes. LLVM's -O2 runs approximately 150 distinct passes. The passes interact: constant propagation creates dead code for DCE to remove; inlining exposes new opportunities for LICM; DCE eliminates branches that enable more constant propagation. This cascading is a feature, not a bug, but it means pass order matters enormously.

The phase ordering problem: There is no universally optimal order for optimization passes. This is theoretically undecidable in general, and in practice compilers use carefully hand-tuned sequences that work well on benchmarks. Research into ML-guided phase ordering (AutoTVM, MLGO, CompilerGym) has shown that learned orderings can outperform hand-tuned sequences on specific workloads.

Canonical pipeline sketch (LLVM -O2):

1. Mem2Reg (promote memory to SSA registers)
2. InstCombine (peephole algebraic simplifications)
3. SimplifyCFG (fold branches, merge blocks)
4. SROA (scalar replacement of aggregates)
5. EarlyCSE (early common subexpression elimination)
6. Inliner (function inlining)
7. ... (repeat the above in an SCC order over the call graph) ...
8. LICM (loop-invariant code motion)
9. IndVarSimplify (induction variable canonicalization)
10. LoopVectorize (auto-vectorization)
11. SLPVectorize (superword-level parallelism)
12. GVN (global value numbering — SSA-based CSE)
13. SCCP (sparse conditional constant propagation)
14. DCE / ADCE (aggressive dead code elimination)

Modern compilers (especially for ML workloads — XLA, TVM, Halide) organize passes in a middle-end IR specifically designed for optimization (MLIR uses a hierarchy of dialects), and allow user-defined passes to slot in.

// LLVM opt command: run specific passes manually
// clang -O0 -emit-llvm -S foo.c -o foo.ll
// opt -mem2reg -instcombine -simplifycfg \
//     -gvn -sccp -adce -o foo_opt.bc foo.ll
// llc foo_opt.bc -o foo.s

// To see what passes -O2 runs:
// clang -O2 -mllvm -print-after-all foo.c 2>&1 | grep 'IR Dump'

// Modern MLIR pipeline snippet (pseudocode):
// PassManager pm;
// pm.addPass(createInlinerPass());
// pm.addPass(createCSEPass());
// pm.addPass(createLoopFusionPass());
// pm.addPass(createVectorizationPass());
// pm.run(module);