Polyhedral compilation without polyhedra

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: How to model various aspects of a piece of code using Presburger sets and relations. Which basic operations are available on such sets and relations, without going into details on how these operations are implemented. How to use these operations to mainly analyze but also transform programs. Which tools are available for polyhedral compilation. A small selection of some of the results that may be achieved through polyhedral compilation. 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.status: publishe