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
Complete list of metadatas

Cited literature [47 references]  Display  Hide  Download

https://hal.inria.fr/hal-00963590
Contributor : Fabrice Rastello <>
Submitted on : Friday, March 21, 2014 - 3:08:40 PM
Last modification on : Wednesday, April 11, 2018 - 1:56:05 AM
Long-term archiving on : Saturday, June 21, 2014 - 11:47:01 AM

Files

RR-8491.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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⟩

Share

Metrics

Record views

602

Files downloads

728