CR10 - Advanced Compilation

Prerequisites

• Undergraduate compiler and architecture course.
• Strong interest for both applied and theoretical research.

Overview

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 (part 3).

Course Outline

1. Introduction
   • Target architectures (parallelism, memory hierarchy, programmable logic, VLSI)
   • Principles of program optimization (operation, dependence, scheduling, allocation)
   • Mathematical basis (cone, polyhedron, affine lattice, duality)
2. 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.
3. Back-end 1, compiling hardware: high-level synthesis
   • principles of high-level synthesis
   • pipeline construction
4. 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)

Evaluation

Organization

1. 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.
2. 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.
3. 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 available.
   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.

References

• 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).