Parameterized Construction of Program Representations for Sparse Dataflow Analyses

Abstract : Data-flow analyses usually associate information with control flow regions. Informally, if these regions are too small, like a point between two consecutive statements, we call the analysis dense. On the other hand, if these regions include many such points, then we call it sparse. This paper presents a systematic method to build program representations that support sparse analyses. To pave the way to this framework we clarify the bibliography about well-known intermediate program representations. We show that our approach, up to parameter choice, subsumes many of these representations, such as the SSA, SSI and e-SSA forms. In particular, our algorithms are faster, simpler and more frugal than the previous techniques used to construct SSI - Static Single Information - form programs. We produce intermediate representations isomorphic to Choi et al.'s Sparse Evaluation Graphs (SEG) for the family of data-flow problems that can be partitioned by variables. However, contrary to SEGs, we can handle - sparsely - problems that are not in this family. We have tested our ideas in the LLVM compiler, comparing different program representations in terms of size and construction time.
Type de document :
Communication dans un congrès
CC 2014 - 23rd International Conference on Compiler Construction, 2014, Grenoble, France. Springer, 2014
Liste complète des métadonnées

https://hal.inria.fr/hal-00921461
Contributeur : Fabrice Rastello <>
Soumis le : vendredi 20 décembre 2013 - 14:29:59
Dernière modification le : vendredi 20 avril 2018 - 15:44:25

Identifiants

  • HAL Id : hal-00921461, version 1

Collections

Citation

André Tavares, Fabrice Rastello, Benoit Boissinot, Fernando Pereira. Parameterized Construction of Program Representations for Sparse Dataflow Analyses. CC 2014 - 23rd International Conference on Compiler Construction, 2014, Grenoble, France. Springer, 2014. 〈hal-00921461〉

Partager

Métriques

Consultations de la notice

276