ECE 5544 - Compiler Optimizations

Course Description

Overview of compilation and compiler optimizations. Design and internal organization of the Low-Level Virtual Machine compiler infrastructure. Static Single Assignment. Dataflow 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.

Pre: Graduate standing. (3H, 3C)

Why take this course?

With computer hardware reaching a limit on the single-threaded CPU performance, chip vendors are manufacturing an array of diverse architectures, ranging from those with high degrees of hardware parallelism (e.g., multicores) to those with high degrees of heterogeneity (e.g., graphics processing units or GPUs). Improving application software performance on such hardware without sacrificing programmability requires significant degree of compile-time code optimizations. The science of code optimization – the central course objective – therefore has significant and immediate practical value and constitutes a basic knowledge of existing compiler optimizations.

Learning Objectives

• Specify dataflow analysis techniques for reaching definitions, live variable analysis, and available expressions
• Illustrate dataflow analysis foundations including lattice theory and iterative algorithms for general frameworks
• Generalize dataflow analysis to non-separable dataflow analysis including that for constant propagation and folding, faint variable analysis, and points-to may/must analysis
• Formulate loop-invariant code motion, lazy code motion, Static Single Assignment (SSA) construction and SSA-based optimizations, and register allocation and coalescing
• Analyze pointer aliases and points-to objects including using Anderson’s and Steensgaard’s algorithms, and liveness of heap objects
• 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