Scalable array SSA and array data flow analysis

Silvius Rus; Guobin He; Lawrence Rauchwerger

doi:10.1007/978-3-540-69330-7_27

Scalable array SSA and array data flow analysis

Silvius Rus, Guobin He, Lawrence Rauchwerger

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers
Pages	397-412
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-540-69330-7_27
State	Published - 2006
Externally published	Yes
Event	18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005 - Hawthorne, NY, United States Duration: Oct 20 2005 → Oct 22 2005

Publication series

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

Other

Other	18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005
Country	United States
City	Hawthorne, NY
Period	10/20/05 → 10/22/05

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-69330-7_27

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

Scalable array SSA and array data flow analysis. / Rus, Silvius; He, Guobin; Rauchwerger, Lawrence.

Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers. 2006. p. 397-412 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4339 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4339 LNCS, pp. 397-412, 18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005, Hawthorne, NY, United States, 10/20/05. https://doi.org/10.1007/978-3-540-69330-7_27

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

Rus, Silvius ; He, Guobin ; Rauchwerger, Lawrence. / Scalable array SSA and array data flow analysis. Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers. 2006. pp. 397-412 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{d0d330104aac44efb1de05698553aa67,

title = "Scalable array SSA and array data flow analysis",

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.",

author = "Silvius Rus and Guobin He and Lawrence Rauchwerger",

note = "Copyright: Copyright 2011 Elsevier B.V., All rights reserved.; 18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005 ; Conference date: 20-10-2005 Through 22-10-2005",

year = "2006",

doi = "10.1007/978-3-540-69330-7_27",

language = "English (US)",

isbn = "3540693297",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "397--412",

booktitle = "Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers",

}

TY - GEN

T1 - Scalable array SSA and array data flow analysis

AU - Rus, Silvius

AU - He, Guobin

AU - Rauchwerger, Lawrence

PY - 2006

Y1 - 2006

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=43949132122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43949132122&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-69330-7_27

DO - 10.1007/978-3-540-69330-7_27

M3 - Conference contribution

AN - SCOPUS:43949132122

SN - 3540693297

SN - 9783540693291

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 397

EP - 412

BT - Languages and Compilers for Parallel Computing - 18th International Workshop, LCPC 2005, Revised Selected Papers

T2 - 18th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2005

Y2 - 20 October 2005 through 22 October 2005

ER -