Intermediate code and optimization
Lowering to three-address code, local optimizations such as constant folding and dead code elimination, and control-flow graphs with liveness analysis.
About 5 hours of study
Learning objectives
- Lower expressions and control flow to three-address code
- Fold constants, propagate copies, reuse expressions and remove dead code
- Build control-flow graphs and compute live variables
Lessons
- 1
Three-address code Advanced
Lower the syntax tree to an intermediate representation: simple instructions with at most one operator each, temporaries for partial results, and labels with jumps for loops and conditions.
- 2
Optimizing intermediate code Advanced
Make code faster without changing what it does. Fold constants, propagate known values and copies, simplify with algebra, reuse common subexpressions and delete dead code, all on three-address code.
- 3
Basic blocks, control-flow graphs and liveness Advanced
Split code into basic blocks, connect them into a control-flow graph, find loops and unreachable code, and compute which variables are live with a dataflow analysis repeated until nothing changes.
Module practice
- Compilers: Lower an assignmentEasy
- Compilers: Lower loops and conditionsMedium
- Compilers: Run three-address codeHard
- Compilers: Fold and propagate constantsEasy
- Compilers: Remove dead codeMedium
- Compilers: A local optimizerHard
- Compilers: Find the basic blocksEasy
- Compilers: Build the control-flow graphMedium
- Compilers: Live variablesHard