• Abstract Syntax Trees (AST)
• Intermediate Representations: CFG, three-address code
• Static Single Assignment (SSA)
• Phi nodes and dominance
• Building SSA: renaming, edge splitting
• Optimizations enabled by SSA
• Lowering, codegen interfaces
• IRs in the wild (LLVM, Sea-of-Nodes, MIR/HIR)
• Exercises

• Tree structure mirrors grammar with semantic annotations (types, scopes, source spans).
• ASTs facilitate analysis/transforms before lowering to IR.
• Visitors and pattern-matching simplify tree traversals.

Binary(op, lhs, rhs), Call(callee, args), Let(name, init)

• Control Flow Graph (CFG) of basic blocks; edges model control flow.
• Three-address code (TAC) simplifies expression evaluation and optimizations.
• Form affects optimization power and codegen ease.

t1 = a * 2
if t1 > 10 goto B1 else B2

• Each variable assigned exactly once; new names for new definitions.
• Simplifies dataflow reasoning; enables sparse, powerful analyses.
• Introduces φ (phi) functions to merge control-flow values.

x0 = 0
if (c) x1 = 1 else x2 = 2
x3 = phi(x1, x2)

• Place φ at dominance frontiers of definition sites.
• Dominators: node D dominates N if all paths to N go through D.
• Use IDF (iterated dominance frontier) to compute φ placement.

DF(X) = Union over Y in Succ(X) of (DomFrontier(Y))

• Insert φ at IDFs; perform renaming via DFS with per-variable stacks.
• Edge splitting for critical edges to place φ operands cleanly.
• Pruned SSA reduces φ insertion using live variable info.

• Constant propagation/folding, dead code elimination (DCE).
• Sparse conditional constant propagation (SCCP), GVN, PRE.
• Alias analysis and escape analysis simplified with SSA names.

SCCP: lattice {undef, const(c), overdefined} + sparse worklist on CFG

• Lower SSA to machine IR with explicit registers/moves or to SSA-like virtual regs.
• Deconstruction of φ into parallel copies at block boundaries.
• Maintain debug info (value tracking) across lowering and RA.

• LLVM SSA in a CFG; GVN, SROA, LICM rely on SSA structure.
• Sea-of-Nodes (HotSpot/V8): unified value+control graph enabling global value numbering.
• Rust MIR/HIR multi-level IRs; MLIR for extensible dialect-based IRs.

# Inspect LLVM IR
clang -O0 -S -emit-llvm foo.c -o - | less

1. Implement SSA renaming on a small CFG and insert φ via dominance frontiers.
2. Implement SCCP and compare results pre- and post-SSA.
3. Lower φ nodes into parallel copies and schedule them around critical edges.