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

Lessons

  1. 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. 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. 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

Module quiz

1. How is x = a + b * c lowered to three-address code?
2. What does constant folding do to b = 4 * 2?
3. Which way does dead code elimination walk a block?
4. Which instruction is a leader?
5. What does a back edge in a control-flow graph usually show?
6. What is live in of a block?

‹ Trees, scopes and typesGenerating code ›