Code Optimization in Production Compilers NSWI134, 2019
Office hours: by appointment (prefferably Tuesday or Wednesday). S322 (Malostranské nám. 25, 3rd floor).
- February 20
- Brief history of compilers: from 1950s till today. What are main differences between compilers in 1980s, 90s, 2000s and today. Introduction to open-source compiler projects: GCC, LLVM, Open64, Spider Monkey, Chrome V8
- February 28
- Intermediate languages: design challenges, basic features of a highlevel, midlevel and lowlevel ILs. Type system of Gimple as an example of high-level approach, LLVM as an example of midlevel/lowlevel approach and RTL (a very low-leve IL). Brief mention of WHIRL used by Open64 as an example if IL that can work on multiple levels and MLIR, a multi-level IR being developed by Google for LLVM and Tensorflow.
Some discussion about new architectures such as GCN and ARM SVE.
- March 7
- More on intermediate languages. Control flow graph. Introduction to basic local optimizers: basic-block, super-block and hyper-block based optimizers.
- March 14
- Data-flow analysis and basic iterative dataflow slovers. Formulation of constant-propagation, copy-propagation, constant subexpression ellimination as data-flow problems. Why writting data-flow based compilers is hard. You can check, for example this slides.
- March 14
- No teaching
- March 28
- Single Static Assignment (SSA) form and algorithm for Sparse Conditional Constant Propagation by Wegman and Zadeck. Its use for value range propagation, bitwise constant propagation, forward propagation and other optimizations.
Dominator relation, basic properties (it is a tree!)
- Apr 3
- Basic dominator based optimization. Dominator tree construction by dataflow. Classical SSA construction algorithm.
- Apr 3
- Constant propagation with conditional branches and related algorithms.
- Apr 10
- Dead code elimination using control dependency.
- Apr 24
Value numbering algorithms: partitioning algorithm, RPO algorithm, SCC based algorithm.
- May 1
- New effecient algorithm for SSA construction and early optimization
- May 8
- No teaching
- May 15
- Partial redundancy elimination using lazy code motion, global value numbering based partial redundancy ellimination