Compilers · Cluster
Optimization
Dataflow analysis, inlining, and loop transformations.
- 01 Reaching Definitions and the Monotone Dataflow Framework How a compiler computes which assignments can reach each program point, why the answer is a least fixpoint over a lattice, and where the bitvector approximation stops being exact.
- 02 Live-Variable Analysis and the Backward Direction of Dataflow Liveness runs the dataflow equations against the edges, from uses back to definitions, and the difference between may-liveness and must-liveness decides which optimizations are legal.
- 03 SSA Construction and the Cost of Phi Placement Dominance frontiers decide where phi nodes belong, minimal SSA places too many of them, and pruning by liveness is what keeps the form small enough to optimize.
- 04 Constant Propagation over a Flat Lattice Propagating constants requires a lattice with an explicit top element for "not constant", a meet that never guesses, and an SSA-based solver that avoids the quadratic worklist.
- 05 Inlining Decisions and the Cost Model Behind Them Inlining is chosen by a profitability estimate over caller and callee size, call frequency, and constant-argument opportunities, and every model trades code size against a set of downstream optimizations.
- 06 Escape Analysis and Scalar Replacement of Aggregates Escape analysis decides which allocations never leave a thread or a method, and scalar replacement turns those objects into SSA values so the allocation and its fields disappear entirely.
- 07 Loop-Invariant Code Motion and the Conditions It Needs Hoisting an expression out of a loop requires proving it computes the same value on every iteration, and each of the conditions that license it fails in a way that costs correctness rather than speed.
- 08 Profile-Guided Optimization and Hot-Cold Code Splitting Profile data turns optimization decisions from static guesses into frequency estimates, and splitting cold paths out of hot functions is what converts that knowledge into layout, register, and inlining wins.
- 09 Loop Unrolling, Trip Counts, and the Cost of Code Growth Unrolling by a known factor removes loop overhead and enables scheduling across iterations, but it needs trip-count knowledge, a remainder loop, and a register-pressure check to pay off.
- 10 Dependence Analysis and Polyhedral Loop Transformations Deciding whether two iterations touch the same memory requires a dependence test, and the polyhedral model turns those tests into an integer linear program whose solution drives tiling, skewing, and fusion.