The BRADLEY DEPARTMENT of ELECTRICAL and COMPUTER ENGINEERING

ECE 5544 Compiler Optimizations | ECE | Virginia Tech

Graduate PROGRAMS

Course Information

Description

Overview of compilation and compiler optimizations. Design and internal organization of the Low-Level Virtual Machine compiler infrastructure. Static Single Assignment. Data-flow analysis and techniques for reaching definitions, live variable analysis, and available expressions. Lattice theory and iterative algorithms for general frameworks. Non-separable dataflow analysis including constant propagation and folding, faint variable analysis, and points-to may/must analysis. Loop-invariant code motion and lazy code motion. Static Single Assignment construction and optimizations. Register allocation and coalescing. Pointer analysis using Anderson’s and Steensgaard’s algorithms, and liveness analysis of heap data.

Why take this course?

Learning Objectives

  • 1. Specify data-flow analysis techniques for reaching definitions, live variable analysis, and available expressions
  • 2. Illustrate data-flow analysis foundations including lattice theory and iterative algorithms for general frameworks
  • 3. Generalize data-flow analysis to non-separable data-flow analysis including that for constant propagation and folding, faint variable analysis, and points-to may/must analysis
  • 4. Formulate loop-invariant code motion, lazy code motion, Static Single Assignment (SSA) construction and SSA-based optimizations, and register allocation and coalescing
  • 5. Analyze pointer aliases and points-to objects including using Anderson’s and Steensgaard’s algorithms, and liveness of heap objects
  • 6. Implement Low-Level Virtual Machine (LLVM) passes for analysis and transformations including reaching definitions, live variables, available expressions, loop-invariant code motion, lazy code motion, pointer analysis, and register allocation

Course Topics

Topic

Percentage of Course

1. Overview of compilation and compiler optimizations 5%
2. Design and internal organization of the Low-Level Virtual Machine (LLVM) compiler infrastructure 5%
3. Dataflow analysis techniques for reaching definitions, live variable analysis, and available expressions 15%
4. Foundations of dataflow and iterative algorithms for general frameworks 10%
5. Non-separable dataflow analysis including constant propagation and folding, faint variable analysis, and points-to may/must analysis 10%
6. Loop-invariant code motion and lazy code motion 15%
7. Static Single Assignment (SSA) construction and SSA-based optimizations 15%
8. Register allocation and coalescing 15%
9. Pointer analysis using Anderson’s and Steensgaard’s algorithms and liveness analysis of heap data 10%