Code Transformation and Optimization 2013 (draft)
In modern computer science and engineering, code transformation techniques are critical to achieve the combined goals of combining programmer productivity and program execution efficiency in terms of time and energy. Yet, it is a skill mastered by few – there are less than 1.5 compiler construction expert for every 1000 software engineers, but almost 2 jobs in compilers for every 100 in software engineering!
The course is designed to provide an overview of code transformation, analysis and optimization techniques needed to effectively produce optimized code.
To compiler and EDA tool engineers, the course provides the basic tools to design and implement compilers and other code transformation and analysis tools, as well as an introduction to the most popular modern compiler framework, LLVM.
To software engineers, the course provides a grounding in system software design and development, as well as insights on the benefits and limitations of automation in software engineering. Moreover, as a compiler is a paramount of complex software systems, it provides a hands-on introduction to the design and implementation process for such systems. Finally, many advanced software engineering techniques such as program slicing are implemented on top of algorithms used in compiler construction.
To computer architects and embedded software engineers, the course provides crucial insights on the power and limits of compiler optimization, as well as to the need any processor architecture has of appropriate compilers.
To all computer science students, the course provides a “behind the scenes” view of the operation of software, and its automated manipulation – understanding compilers means being able to write better, more efficient code.
Understand the internal structure of a real-world compiler
Understand the effectiveness and limitations of code analysis and optimization techniques
Be able to construct a full compiler for a toy language, generating assembly code for a RISC architecture
Introduction to Compiler Construction
Why compiling? Compilers vs interpreters
When to compile? JIT, AOT and static compilers
What to compile? Compilation units
Where to compile? Cross-compilation and split compilation
Overview of a compiler framework
Lexical analysis & parsing (review)
Statement and Data Structure Lowering
Optimization: machine independent and machine-dependent
Reading: Compiler Construction
Reading: Program Dependence Graph
Reading: The SUIF Compiler Framework
Semantic Analysis & Type Checking
Reading: Garbage Collection
Reading: Low-level Optimization
Reading: Dataflow Optimizations
Reading: Linear Scan Register Allocation
Parallelization and other optimization techniques
Reading: Program Optimization
Reading: Alias Analysis
Reading: Cache Optimization
Advanced Optimization Techniques: Polyhedral Transformations
The LLVM Compiler Framework
The papers presented in this bibliography are mostly for those who wish to get deeper insight on a specific topic.
LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, by C. Lattner and V. Adve.
The Program Dependence Graph and Its Use in Optimization, by J. Ferrante et al.
The Basic SUIF Programming Guide, by G. Aigner et al.
Interprocedural pointer alias analysis, by M. Hind et. al.
Linear Scan Register Allocation, by M. Poletto and V. Sarkar.
Compiler Transformations for High-Performance Computing, by D. Bacon et al.
A Retrospective: A Data Locality Optimizing Algorithm, by M. S. Lam.
Uniprocessor Garbage Collection Techniques: a complete survey of Garbage Collection by P. Wilson.