CR10 - Advanced Compilation
Christophe Alias (CR Inria, contact person), Fabrice Rastello (CR Inria), Florent de Dinechin (Prof. INSA-Lyon).
- Undergraduate compiler and architecture course.
- Strong interest for both applied and theoretical research.
Modern programming languages offer a level of abstract allowing to implement
A compiler translates a high-level program into a circuit description
(hardware) or a sequence of machine instructions (software). Hence,
compilers make possible the existence of computing systems and even
computer science. But with big power comes big responsabilities. The
translation must be correct (semantic preserving) and efficient in
terms of ressource usage (performance, consumption, size,
etc). However, the increasing complexity of target machines
(many-cores, GPU, etc) and the critical position of the compilers in
the developement chain make challenging to develop efficient
translation schemes. To avoid reinventing the wheel, theoretical
models and generic frameworks for program analysis and optimization
are designed by compiler researchers.
This course provides a panoramic view of such optimization models and
frameworks, which use both geometric and algebraic program abstractions
(part 1 and 2). Also, we show how such models can be used to
produce efficient hardware in the context of high-level synthesis
- Target architectures (parallelism, memory hierarchy, programmable logic, VLSI)
- Principles of program optimization (operation, dependence, scheduling, allocation)
- Mathematical basis (cone, polyhedron, affine lattice, duality)
- Front-end: polyhedral code analysis and optimization
- Polyhedral model: a theory of all-affine analysis
- Dependence analysis (array dataflow analysis, dynamic single assignement form, SAREs)
- Scheduling (cone method, greedy algorithm, loop tiling)
- Memory Allocation (element-wise liveness analysis, half-width method)
- Lab (TP): polyhedral programming with ISL.
- Back-end 1, compiling hardware: high-level synthesis
- principles of high-level synthesis
- pipeline construction
- Back-end 2, compiling software: SSA-based analysis and optimizations
- sparse non-relational data-flow analysis (bi-directionality, SSI)
- predication (speculation, if-conversion, gated-SSA, psi-SSA)
- aliasing (iterative analysis, points-to, shape, H-SSA)
Each student must:
- Choose a paper among the followings. Two students cannot read the same paper.
Send an email with your choice to Christophe.Alias at ens-lyon.fr by November 24.
- Write a small synthesis report of 2 pages maximum by filling out this [LaTeX template] (mandatory).
It is strongly encouraged to look for, read (or at least browse) and discuss additional related papers along with the paper you present.
Send the .pdf of your report to Christophe.Alias at ens-lyon.fr by December 7.
This deadline is strict, no report will be accepted later.
- Prepare a presentation of 15 minutes.
The presentation must sum up the paper and the analysis presented
in the report, and will be followed by questions.
The quality of the presentation (slides, oral presentation) be evaluated as well. Some tips are available here.
Presentations will be held on the week of December 8 and on
the week of December 15, precise dates and places will be given
later. A laptop connected to a beamer and a board will be
Send the .pdf of your slides to Christophe.Alias at ens-lyon.fr
by December 7. Again, this deadline is strict. No
slides will be accepted later.
- Andrew Appel, "Modern Compiler Implementation", (Tiger book), compiler basics.
- Jingling Xue, "Loop tiling for parallelism", (part 1).
Alain Darte, Yves Robert, Frederic Vivien, "Scheduling and Automatic Parallelization", (part 1).
- Joao Cardoso, Pedro Diniz, "Compilation Techniques for Reconfigurable Architectures", (part 2).
- Fabrice Rastello, Florent Bouchez, "SSA-based Compiler Design" (part 3).