Ing Ind - Inf (Mag.)(ord. 270) - MI (263) MUSIC AND ACOUSTIC ENGINEERING
090957 - CODE TRANSFORMATION AND OPTIMIZATION
Ing Ind - Inf (Mag.)(ord. 270) - MI (481) COMPUTER SCIENCE AND ENGINEERING - INGEGNERIA INFORMATICA
090957 - CODE TRANSFORMATION AND OPTIMIZATION
Code Transformation and Optimization
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.
Risultati di apprendimento attesi
Expected Learning Outcomes
Knowledge and understanding
Understand the internal structure of a real-world compiler as a pipeline of passes, including its main components (front-end: parser, lexer; mid-end: optimizers; back-end: code generator, register allocator, instruction scheduler).
Understand the effectiveness and limitations of code analysis and optimization techniques (focusing in particular on loop transformation and data flow analysis)
Understand the main issues related to the linking phase
Applying knowledge and understanding
Be able to construct a full compiler for a toy language, generating assembly code for a RISC architecture.
Get familiarity with the LLVM compiler framework (an industry-grade, open source compiler).
Analyse and understand the effectiveness of specific code analysis and transformation techniques.
Define the architecture of a compiler framework and/or of specific compiler passes within a give infrastructure.
Understand the pitfalls and tradeoffs of compiler development (e.g., ease of debugging vs global performance optimization).
Develop the ability to communicate complex algorithmic concepts within a short timeframe.
Lifelong learning skills
Learn how to develop in practice a large scale project, understanding the importance of early assessing pitfalls and tradeoffs in development.
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
The Abstract Syntax Tree
Basic Blocks and branches
The Control Flow Graph
The Static Single Assignment Form
Reading: Program Dependence Graph
Reading: The SUIF Compiler Framework
Semantic Analysis & Type Checking
Data Memory layout
Dynamic Memory allocation
Reading: Garbage Collection
Code generation techniques: CISC and RISC processors
Transforming the Abstract Syntax Tree into a Control Flow Graph
Design and implementation of the symbol table
Function call translation
Register allocation (linear scan)
ARM code generation (table-based)
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.
The course is mostly self-contained. Knowledge of imperative and object-oriented programming (as provided in the Laurea in Ingegneria Informatica) is necessary, and an understanding of parsing techniques is useful (however, the necessary concepts of recursive descent parsing are introduced in the first lecture and observed in practice in the first laboratory). Also, a basic understanding of computational complexity (once more, as provided in Laurea in Ingegneria Informatica) is useful.
The project/laboratory work can be conducted in Python or C++.
Modalità di valutazione
Evaluation is performed through a combination of oral exam and project work.
Type of Assessment
The oral exam consists of a discussion of the topics covered in the course, including theoretical questions and questions aimed at assessing the ability of the student to connect different topics within the course syllabus.
Assessment of laboratorial artefacts
The project work can be taken in groups of one to three students, and in the following two modes:
An independent project activity, consisting in the implementation of an optimization or analysis pass in the LLVM compiler framework (suggested only for students with previous experience in C/C++ programming);
A supervised project activity, consisting in the implementation of a compiler for a toy language targeting the ARM assembly language.
Andrew Appel with Jens Palsberg, Modern compiler implementation in Java, Editore: Cambridge University Press, Anno edizione: 2002 Note:
The similar, but earlier, book "Modern compiler implementation in C" by Appel is available online for free download.
Aho, Lam, Sethi, and Ullman, Compilers: principles, techniques and tools, Editore: Prentice-Hall, Anno edizione: 2006 Note:
We use only Chapter 11
Tipo Forma Didattica
Ore di attività svolte in aula
Ore di studio autonome
Laboratorio Di Progetto
Informazioni in lingua inglese a supporto dell'internazionalizzazione
Insegnamento erogato in lingua
Disponibilità di materiale didattico/slides in lingua inglese
Disponibilità di libri di testo/bibliografia in lingua inglese
Possibilità di sostenere l'esame in lingua inglese
Disponibilità di supporto didattico in lingua inglese