• Goals and trade-offs
• Common Subexpression Elimination (CSE)
• Dead Code Elimination (DCE)
• Loop-Invariant Code Motion (LICM)
• Inlining
• Pass interactions and ordering
• Cost models and heuristics
• Exercises

• Reduce runtime, code size, or energy; maintain correctness and debug-ability.
• Beware of pathological slowdowns from code size growth (I-cache pressure).
• Profile-guided and cache-aware choices often win in practice.

• Replace repeated equivalent computations with a single computed value.
• Global Value Numbering (GVN) detects equivalences across blocks.
• Alias/memory dependence constrain load CSE; use alias analysis and MDSSA.

t1 = a*b; ...; t2 = a*b  ⇒  t2 := t1 (if operands and flags identical, and no intervening defs)

• Remove computations whose results are never used and have no side effects.
• Sparse DCE on SSA leverages use-def chains; aggressive DCE relies on side-effect analysis.
• Be careful with volatile/atomic operations and observable behavior.

if a then x=1 else x=2; return 0  ⇒  assignments to x are dead

• Hoist computations invariant within a loop to preheaders; sink post-invariant code.
• Requires dominance, alias checks, and safety (exceptions, traps).
• Combine with induction variable simplification and strength reduction.

for i in 0..n: y = a*b; z[i] = y + i  ⇒  y = a*b; for i: z[i] = y + i

• Replace call sites with callee body; exposes more optimization but grows code size.
• Heuristics: callee size, hotness (PGO), devirtualization opportunities, recursion limits.
• Inline cost must consider register pressure and I-cache misses.

inline small hot getters; avoid inlining large cold functions

• Run passes in loops: inline → CSE/DCE/GVN → LICM → loop unroll/vectorize → cleanup.
• Preserve analyses or rebuild as needed; be aware of invalidation costs.
• IR-specific pipelines (LLVM new pass manager, etc.).

• Static models approximate cycles/memory; dynamic (PGO) uses profiles.
• Model target ISA costs (latency/throughput), cache behavior, and branch prediction.
• Guard against code-size explosions with thresholds.

1. Implement local CSE on a basic block; extend to global via GVN.
2. Implement sparse DCE on SSA and test against tricky side-effect cases.
3. Implement LICM with alias checks and hoist/sink across loop nests.