Splitting Polyhedra to Generate More Efficient Code: Efficient Code Generation in the Polyhedral Model is Harder Than We Thought

Harenome Razanajato 1, 2 Vincent Loechner 1, 2 Cédric Bastoul 1, 2
2 CAMUS - Compilation pour les Architectures MUlti-coeurS
Inria Nancy - Grand Est, ICube - Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie
Abstract : Code generation in the polyhedral model takes as input a union of Z-polyhedra and produces code scanning all of them. Modern code generation tools are heavily relying on polyhedral operations to perform this task. However, these operations are typically provided by general-purpose poly- hedral libraries that are not specifically designed to address the code generation problem. In particular, (unions of) poly- hedra may be represented in various mathematically equiv- alent ways which may have different properties with respect to code generation. In this paper, we investigate this prob- lem and try to find the best representation of polyhedra to generate efficient code. We present two contributions. First we demonstrate that this problem has been largely under-estimated, showing sig- nificant control overhead deviations when using different representations of the same polyhedra. Second, we propose an improvement to the main algorithm of the state-of-the-art code generation tool CLooG. It generates code with fewer tests in the inner loops, and aims to reduce control overhead and to simplify vectorization for the compiler, at the cost of a larger code size. It is based on a smart splitting of the union of polyhedra while recursing on the dimensions. We implemented our algorithm in CLooG/PolyLib, and com- pared the performance and size of the generated code to the CLooG/isl version.
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download

Contributor : Vincent Loechner <>
Submitted on : Friday, April 14, 2017 - 3:22:36 PM
Last modification on : Saturday, October 27, 2018 - 1:23:58 AM
Long-term archiving on : Saturday, July 15, 2017 - 3:44:37 PM


Files produced by the author(s)


  • HAL Id : hal-01505764, version 1


Harenome Razanajato, Vincent Loechner, Cédric Bastoul. Splitting Polyhedra to Generate More Efficient Code: Efficient Code Generation in the Polyhedral Model is Harder Than We Thought. IMPACT 2017, 7th International Workshop on Polyhedral Compilation Techniques, Jan 2017, Stockholm, Sweden. ⟨hal-01505764⟩



Record views


Files downloads