A Tour of Program Optimization
summary
Presents a concrete taxonomy: program optimization splits into transformation (term rewriting, local rewrites, termination and confluence proofs) and synthesis (composition, instruction selection). Shows four algorithms: term rewriting, dynamic‑programming instruction selection (optimal tree covering), e‑graphs / equality saturation (monotonic growth, keep old terms, extract best via DP and emit equivalence proof), and volcano query optimization (rewrites + DP). Notes e‑graphs work but carry heavy state so far, so they do not yet replace handwritten LLVM instcombine.
AI-written summary · about
chapters (8)
- 0:00Introduction and overview
- 3:23Defining program optimization
- 10:51Overview of optimization techniques
- 12:26Term rewriting basics
- 19:31Instruction selection
- 23:16Equality saturation
- 28:13Query optimization
- 31:18Conclusion and Q&A
related talks
21mVerifying term graph optimizations using Isabelle/HOL
20mOptimal Program Synthesis via Abstract Interpretation
33mA Historical Perspective on Program Transformation and Recent Developments (Invi...
56mOn Type-Based Techniques for Program Manipulation
39mAsk Me Anything with Alex Aiken
52mUnderstanding Compiler Optimization
15mScaling Optimization Over Uncertainty via Compilation
15mCoarsening Optimization for Differentiable Programming