Code Optimization in Production Compilers NSWI134, 2019

Jan Hubička,

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