The polyhedral model is a powerful framework for automatic
optimization and parallelization. It is based on an algebraic
representation of programs, allowing to construct and search for
complex sequences of optimizations. This model is now mature and
reaches production compilers. The main limitation of the
polyhedral model is known to be its restriction to statically
predictable, loop-based program parts. This paper removes this
limitation, allowing to operate on general data-dependent
control-flow. We embed control and exit predicates as
first-class citizens of the algebraic representation, from
program analysis to code generation. Complementing previous
(partial) attempts in this direction, our work concentrates on
extending the code generation step and does not compromise the
expressiveness of the model. We present experimental evidence
that our extension is relevant for program optimization and
parallelization, showing performance improvements on benchmarks
that were thought to be out of reach of the polyhedral model.
%0 Book Section
%1 Benabderrahmane2010-dz
%A Benabderrahmane, Mohamed-Walid
%A Pouchet, Louis-Noël
%A Cohen, Albert
%A Bastoul, Cédric
%B Compiler Construction
%D 2010
%I Springer Berlin Heidelberg
%K Polyhedral_model To_Read
%P 283--303
%T The Polyhedral Model Is More Widely Applicable Than You Think
%X The polyhedral model is a powerful framework for automatic
optimization and parallelization. It is based on an algebraic
representation of programs, allowing to construct and search for
complex sequences of optimizations. This model is now mature and
reaches production compilers. The main limitation of the
polyhedral model is known to be its restriction to statically
predictable, loop-based program parts. This paper removes this
limitation, allowing to operate on general data-dependent
control-flow. We embed control and exit predicates as
first-class citizens of the algebraic representation, from
program analysis to code generation. Complementing previous
(partial) attempts in this direction, our work concentrates on
extending the code generation step and does not compromise the
expressiveness of the model. We present experimental evidence
that our extension is relevant for program optimization and
parallelization, showing performance improvements on benchmarks
that were thought to be out of reach of the polyhedral model.
@incollection{Benabderrahmane2010-dz,
abstract = {The polyhedral model is a powerful framework for automatic
optimization and parallelization. It is based on an algebraic
representation of programs, allowing to construct and search for
complex sequences of optimizations. This model is now mature and
reaches production compilers. The main limitation of the
polyhedral model is known to be its restriction to statically
predictable, loop-based program parts. This paper removes this
limitation, allowing to operate on general data-dependent
control-flow. We embed control and exit predicates as
first-class citizens of the algebraic representation, from
program analysis to code generation. Complementing previous
(partial) attempts in this direction, our work concentrates on
extending the code generation step and does not compromise the
expressiveness of the model. We present experimental evidence
that our extension is relevant for program optimization and
parallelization, showing performance improvements on benchmarks
that were thought to be out of reach of the polyhedral model.},
added-at = {2015-04-11T18:41:09.000+0200},
author = {Benabderrahmane, Mohamed-Walid and Pouchet, Louis-No{\"{e}}l and Cohen, Albert and Bastoul, C\'{e}dric},
biburl = {https://www.bibsonomy.org/bibtex/213e7c61474b41a9313a6f6c09118b889/christophv},
booktitle = {Compiler Construction},
interhash = {64bfaf6d015df1ba2038a102874aae0b},
intrahash = {13e7c61474b41a9313a6f6c09118b889},
keywords = {Polyhedral_model To_Read},
pages = {283--303},
publisher = {Springer Berlin Heidelberg},
series = {Lecture Notes in Computer Science},
timestamp = {2015-04-11T18:41:09.000+0200},
title = {The Polyhedral Model Is More Widely Applicable Than You Think},
year = 2010
}