E0255 Compiler Design

Grading

• Asst-1: 25% (Due: 27-Feb, 5 pm)
• Mid-term: 20% (13-Feb-2025, 9:30--11am)
• Asst-2 (mid-Apr)
• End-term: 30%

Topics

• Introduction to Compilers
  • Compilers: evolution
  • Compiler Intermediate Representations (IRs)
  • Compilers in the 21st century - Intro
• Key structures for compiler analysis
  • Basic blocks
  • Control flow graph
  • Dependence Graph
  • Dominators
  • Dominator tree, ...
• Dataflow Analysis
  • Introduction
  • Forward dataflow analysis, Backward dataflow analysis
  • Reaching definitions, Available expressions
• SSA (Static Single Assignment)
• Scalar Optimizations (traditional) using SSA and otherwise
• Optimization and Parallelization
  • Characteristics of Modern Hardware/Architectures, Multicore architectures, Accelerators (GPUs, FPGAs), Unconventional parallel architectures
  • Dependence Analysis
  • Loop Optimizations, Loop Transformations
  • Cache Locality Optimization
  • Parallelism, Loop Parallelization
  • Code Generation
  • Vectorization
  • Other Program Transformations for Performance, Parallelism and Productivity
• MLIR
  • Introduction
  • Basic concepts in compiler IR design
  • Core IR structures
  • Affine Abstractions in MLIR
• Register Allocation
  • Introduction
  • Graph Coloring and Register Allocation
  • Linear Scan
• Modern Programming Languages, Domain-specific Languages
• Challenges in Compiler Design in the 21st Century

References and Downloads

• Course introductory class
• Chapter 11 - Compilers (second edition) - Aho, Lam, Sethi, and Ullman
• Control flow analysis
• Data flow analysis
• Static Single Assignment
• On loops, dominators, and dominance frontiers
• Conditional Constant Propagation on SSA
  
• MLIR introduction
• Mid-level Compiler Optimizations

Additional Reading

• The Omega Test
• Analytical Modeling Is Enough for High-Performance BLIS
  https://dl.acm.org/citation.cfm?id=2925987
  Low et al, ACM TOMS 2016.
  
• LLVM documentation