A Conservative Approach to Manipulate Data-Dependent Control Flow in the Polyhedral Model

Mohamed-Walid Benabderrahmane and Louis-Noel Pouchet
Advisors: Albert Cohen and Cedric Bastoul

ALCHEMY Group, INRIA Saclay Ile-de-France and Paris-Sud 11 University

The polyhedral model is a powerful framework for automatic optimization and parallelization. It is based on an algebraic representation of programs, allowing to achieve exact data dependence analysis and to seamlessly apply complex sequences of optimizations. This model is now quite mature and reaches production compilers such as GCC 4.4 and its GRAPHITE framework. The main limitation of the polyhedral model is known to be its restriction to highly regular loop-based program sub-parts. In our work, we show how to go beyond this limitation by a natural extension that allows the polyhedral model to manipulate and optimize most of the full function bodies encountered in standard programs.

We deliver a complete extended polyhedral framework and we present experimental evidence that our extension is relevant for general program optimization and parallelization, allowing to improve performance on a much broader class of programs. Modern polyhedral optimization algorithms are used out-of-the-box on programs that were previously out of reach of the standard framework.

Long Abstract

Back to Program