Scalable array SSA and array data flow analysis

Silvius Rus, Guobin He, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Static Single Assignment (SSA) has become the intermediate program representation of choice in most modern compilers because it enables efficient data flow analysis of scalars and thus leads to better scalar optimizations. Unfortunately not much progress has been achieved in applying the same techniques to array data flow analysis, a very important and potentially powerful technology. In this paper we propose to improve the applicability of previous efforts in array SSA through the use of a symbolic memory access descriptor that can aggregate the accesses to the elements of an array over large, interprocedural program contexts. We then show the power of our new representation by using it to implement a basic data flow algorithm, reaching definitions. Finally we apply this analysis to array constant propagation and show performance improvement (speedups) for benchmark codes.

Original languageEnglish (US)
Title of host publicationLanguages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers
Pages397-412
Number of pages16
DOIs
StatePublished - Dec 1 2006
Externally publishedYes
Event18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005 - Hawthorne, NY, United States
Duration: Oct 20 2005Oct 22 2005

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4339 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005
CountryUnited States
CityHawthorne, NY
Period10/20/0510/22/05

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Scalable array SSA and array data flow analysis'. Together they form a unique fingerprint.

  • Cite this

    Rus, S., He, G., & Rauchwerger, L. (2006). Scalable array SSA and array data flow analysis. In Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers (pp. 397-412). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4339 LNCS). https://doi.org/10.1007/978-3-540-69330-7_27