Polyhedral Compilation without Polyhedra

Tutorial at HiPEAC 2015 (January 20, 2015) Room G109

Polyhedral compilation is widely used in high-level synthesis tools and in production compilers such as gcc, LLVM and IBM/XL and is still being actively developed by several research groups across the globe, resulting in highly attended IMPACT workshops and a recent polyhedral school. It is based on the polyhedral model, a powerful abstraction for analyzing and transforming (parts of) programs that are "sufficiently regular". The key feature of this model is that it is instance based, allowing for a representation and treatment of individual dynamic executions of a statement inside a loop nest and/or individual array elements. The name of the model derives from the mathematical objects called polyhedra that are used internally to describe these instances. These polyhedra are often represented using matrices, giving the impression to outsiders that the polyhedral model is difficult to use.

In this tutorial, we follow the tradition of the Omega Project and use a slightly higher-level representation based on integer tuples bounded by quasi-affine constraints, which we call named Presburger sets. In particular, we will address the following topics:

An earlier version of part of this tutorial was presented as the first half of a lecture at the polyhedral school, but a lot of extra material was added, mainly about dependence and dataflow analysis.


Register for HiPEAC and select the tutorial.


The tutorial will take place in room G109 (and not in room E001 as previously announced).

Preparing for the tutorial

The tutorial will include a (small) number of hands-on exercises using iscc. You may want to install the barvinok package on your laptop beforehand using the following instructions. (More detailed instructions are available in the README of the barvinok package.)
sudo apt-get install libgmp3-dev libntl-dev rlwrap # On Ubuntu
wget http://barvinok.gforge.inria.fr/barvinok-0.37.tar.bz2
tar xf barvinok-0.37.tar.bz2
cd barvinok-0.37/
./configure --without-glpk
make -j 4
rlwrap ./iscc # or just ./iscc if you don't have rlwrap
Alternatively, you can use the web interface.


demo inputs


Sven Verdoolaege

Sven Verdoolaege is a senior researcher at INRIA (France). In general, his main research interests are in Polyhedral Compilation. He earned his master degrees in Computer Science (1998) and Artificial Intelligence (1999) as well as his PhD on polyhedral loop transformations and counting integer points in polyhedra in Computer Science (2005) from the Katholieke Universiteit Leuven (Belgium). He continued his research on integer point counting, contributing to primal and weighted counting algorithms. As a postdoc, he successively investigated polyhedral process networks, including non-affine extensions, at Leiden University (Netherlands) and equivalence verification at KU Leuven (Belgium). From 2010, he has been conducting research in the group of Albert Cohen at INRIA and ENS (France) on topics such as transitive closures and parallelization for GPUs. His research has culminated in various widely used software packages such as isl, an integer set and polyhedral compilation library; barvinok, a library for (weighted) counting of integer sets; pet, a polyhedral parser; and PPCG, a polyhedral parallelizer.

Tobias Grosser

Tobias is a postdoctoral researcher at ETH Zürich interested in program optimization for parallel architectures. He received his Diploma from the University of Passau (Germany), where he started his work on automatic program transformations using polyhedral modeling. Working in an ENS/INRIA research lab (France) with Albert Cohen and Sven Verdoolaege he received his PhD from Universite Pierre et Marie Curie for work on the efficient execution of stencil computations and the development of new integer set based code generation abstractions.

For his PhD Tobias has been awarded a prestigious 3-year Google European Doctoral Fellowship. He has been interning at ARM, AMD and Google and spent six month as a research scholar at Ohio State University. As an active contributer to LLVM and gcc, he leads the development of the Polly loop optimization infrastructure, mentors PhD and Master students in the context of Google Summer of code projects and regularly participates to the organization of the yearly European LLVM conference.