Final Topics

Design time, compile time, run time

Naming

• Sheafs of symbol tables

• Scoped name resolution with static coordates

• Name resolution for procedures calls with activation records

• Name resolution for object-oriented languages (dynamic dispatch)

Intermediate Representations

• Linear IRs: Basic blocks, quadruples

• Graphical IRs: Abstract syntax trees

• Hybrid IRs: Control-flow graphs

Storage

• Stacks and activation records

• Heap-allocated memory and garbage collection

• Object layout

Local algorithms

• Instruction scheduling

  • Dependency graphs

  • Weighted distance to root

  • List scheduling

• Register allocation (at a high level)

Superlocal and global algorithms

• Data-flow analysis (fixed-point computations) on control-flow graphs

  • Using frequency estimates

• Global instruction scheduling

  • Extended basic blocks

  • Superlocal scheduling (but not trace scheduling)

  • Compensation code

• Global register allocation

  • Live ranges in control-flow graphs

  • Interference graphs (but not coalescing)

  • Graph coloring as register allocation

  • Chaitin-Briggs coloring algorithm