Analysis of irregular single-indexed array accesses and its applications in compiler optimizations

Yuan Lin, David A Padua

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

Abstract

Many compiler techniques require analysis of array subscripts to determine whether a transformation is legal. Traditional methods require the array subscript expressions to be expressed as closed form expressions of loop indices. Most methods further require the subscript expressions to be linear. However, in sparse/ irregular programs, closed-form expressions of array subscripts are not available. More powerful methods to analyze array subscripts are needed. Array accesses with no closed-form expressions available are called irregular array accesses. In real programs, many irregular array accesses are single-indexed. In this paper, we present techniques to analyze irregular single-indexed array accesses. We show that single-indexed array accesses often have properties that are useful in compiler analysis. We discuss how to use these properties to enhance compiler optimizations. We also demonstrate the application of these techniques in three real-life programs to exploit more implicit parallelism.

Original languageEnglish (US)
Title of host publicationCompiler Construction - 9th International Conference, CC 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000, Proceedings
EditorsDavid A. Watt
PublisherSpringer-Verlag
Pages202-218
Number of pages17
ISBN (Print)354067263X, 9783540672630
StatePublished - Jan 1 2000
Event9th International Conference on Compiler Construction, CC 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000 - Berlin, Germany
Duration: Mar 25 2000Apr 2 2000

Publication series

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

Other

Other9th International Conference on Compiler Construction, CC 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000
CountryGermany
CityBerlin
Period3/25/004/2/00

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Analysis of irregular single-indexed array accesses and its applications in compiler optimizations'. Together they form a unique fingerprint.

Cite this