Building of a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of non-Affine Programs Scalable

Abstract : The polyhedral model has been successfully used in production compilers. Nevertheless, only a very restricted class of applications can benefit from it. Recent proposals investigated how runtime information could be used to apply polyhedral optimization on applications that do not statically fit the model. In this work, we go one step further in that direction. We propose a dynamic analysis that builds a compact polyhedral representation from a program execution. It is able to accurately detect affine dependencies and fixed-stride memory accesses in programs. The analysis scales to real-life applications, which often include some non-affine dependencies and accesses in otherwise affine code. This is enabled by a safe fine-grain polyhedral over-approximation mechanism applied to each analyzed expression. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about potential for complex polyhedral transformations.
Complete list of metadatas

https://hal.inria.fr/hal-01967828
Contributor : Manuel Selva <>
Submitted on : Thursday, January 10, 2019 - 11:04:08 AM
Last modification on : Monday, April 29, 2019 - 11:38:04 AM

File

rr.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01967828, version 2

Citation

Fabian Gruber, Manuel Selva, Diogo Sampaio, Christophe Guillon, Louis-Noël Pouchet, et al.. Building of a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of non-Affine Programs Scalable. [Research Report] RR-9244, CORSE - Compiler Optimization and Run-time Systems. 2019, pp.1-24. ⟨hal-01967828v2⟩

Share

Metrics

Record views

122

Files downloads

440