Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadatas
Contributor : Fabrice Rastello <>
Submitted on : Friday, December 20, 2013 - 2:29:59 PM
Last modification on : Friday, July 17, 2020 - 11:10:23 AM


  • HAL Id : hal-00921461, version 1



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. ⟨hal-00921461⟩



Record views