SPolly: Speculative Optimizations in the Polyhedral Model
by
Johannes Doerfert, Clemens Hammacher, Kevin Streit, Sebastian Hack
Armin Größlinger, Louis-Noël Pouchet (Ed.), Proc. 3rd International Workshop on Polyhedral Compilation Techniques (IMPACT), Pages 55-61, Berlin, Germany, January 2013.
Abstract
The polyhedral model is only applicable to code regions that form static control parts (SCoPs) or slight extensions thereof. To apply polyhedral techniques to a piece of code, the compiler usually checks, by static analysis, whether all SCoP conditions are fulfilled. However, in many codes, the compiler fails to verify that this is the case. In this paper we investigate the rejection causes as reported by Polly, the polyhedral optimizer of a state-of-the-art compiler. We show that many rejections follow from the conservative overapproximation of the employed static analyses. In SPolly, a speculative extension of Polly, we employ the knowledge of runtime features to supersede this overapproximation. All speculatively generated variants form valid SCoPs and are optimizable by the facilities of Polly. Our evaluation shows that SPolly is able to effectively widen the applicability of polyhedral optimization. On the SPEC 2000 suite, the number of optimizable code regions is increased by 131 percent. In 10 out of the 31 benchmarks of the PolyBench suite, SPolly achieves speedups of up to 11-fold as compared to plain Polly.
BibTeX Entry
@inproceedings{doerfert-impact-2013,
title = "{SP}olly: {S}peculative {O}ptimizations in the {P}olyhedral {M}odel",
author = "Johannes Doerfert and Clemens Hammacher and Kevin Streit and Sebastian Hack",
year = "2013",
month = jan,
address = "Berlin, Germany",
booktitle = "Proc. 3rd {I}nternational {W}orkshop on {P}olyhedral {C}ompilation {T}echniques ({IMPACT})",
editors = "Armin Größlinger and Louis-Noël Pouchet",
pages = "55--61",
}