Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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 per variables. However, contrary to SEGs, we can handle - sparsely - problems that are not in this family.
Document type :
Reports (Research report)
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download
Contributor : Fabrice Rastello Connect in order to contact the contributor
Submitted on : Friday, March 21, 2014 - 3:08:40 PM
Last modification on : Wednesday, October 26, 2022 - 8:14:25 AM
Long-term archiving on: : Saturday, June 21, 2014 - 11:47:01 AM


Files produced by the author(s)


  • HAL Id : hal-00963590, version 1
  • ARXIV : 1403.5952


André Tavares, Benoit Boissinot, Fernando Pereira, Fabrice Rastello. Parameterized Construction of Program Representations for Sparse Dataflow Analyses. [Research Report] RR-8491, Inria. 2014, pp.27. ⟨hal-00963590⟩



Record views


Files downloads