Building a Polyhedral Representation from an Instrumented Execution: Making Dynamic Analyses of Non-Affine Programs Scalable - Archive ouverte HAL Access content directly
Journal Articles ACM Transactions on Architecture and Code Optimization Year : 2019

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

(1) , (1) , (1) , (2) , (3) , (1)
1
2
3

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.
Fichier principal
Vignette du fichier
taco-hal.pdf (851.55 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02418987 , version 1 (19-12-2019)

Identifiers

Cite

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, 2019, 16 (4), pp.1-26. ⟨10.1145/3363785⟩. ⟨hal-02418987⟩
100 View
434 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More