Skip to Main content Skip to Navigation

Building 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 the folding-based analysis that, from the output of an instrumented program execution, builds a compact polyhedral representation. It is able to accurately detect affine dependencies, fixed-stride memory accesses and induction variables in programs. It 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. We evaluate our analysis on the entire Rodinia benchmark suite, enabling accurate feedback about potential for complex polyhedral transformations.
Document type :
Journal articles
Complete list of metadatas

Cited literature [46 references]  Display  Hide  Download

https://hal.inria.fr/hal-02418987
Contributor : Manuel Selva <>
Submitted on : Thursday, December 19, 2019 - 11:30:03 AM
Last modification on : Wednesday, January 8, 2020 - 1:12:03 AM
Document(s) archivé(s) le : Friday, March 20, 2020 - 4:23:43 PM

File

taco-hal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Manuel Selva, Fabian Gruber, Diogo Sampaio, Christophe Guillon, Louis-Noël Pouchet, et al.. Building a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of Non-Affine Programs Scalable. ACM Transactions on Architecture and Code Optimization, Association for Computing Machinery, 2019, 16 (4), pp.1-26. ⟨10.1145/3363785⟩. ⟨hal-02418987⟩

Share

Metrics

Record views

38

Files downloads

166