Final Exam Topics

• Design time, compile time, run time

• Naming

  • • Sheafs of symbol tables

    • Scoped name resolution with static coordinates

    • Name resolution for procedures calls with activation records  (at a high level)

    • Name resolution for object-oriented languages (dynamic dispatch)  (at a high level)

• 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  (at a high level)

    • Object layout  (at a high level)

• Local algorithms

  • • Instruction scheduling

      • • Dependency graphs

        • Weighted distance to root

        • List scheduling  (at a high level)

    • Register allocation (at a high level)

• Superlocal and global algorithms 

  • • Data-flow analysis (fixed-point computations) on control-flow graphs  (at a high level)

      • • Frequency estimates

    • Global instruction scheduling  (at a high level)

      • • Extended basic blocks

        • Superlocal scheduling (but not trace scheduling)

        • Compensation code

    • Global register allocation  (at a high level)

      • • Live ranges in control-flow graphs

        • Interference graphs (but not coalescing)

        • Graph coloring as register allocation 

        • Chaitin-Briggs coloring algorithm

• Instruction Selection  (at a high level)

  • Treewalk instruction selection

  • Difficulty of choosing the best instructions