TY - GEN
T1 - Analysis of irregular single-indexed array accesses and its applications in compiler optimizations
AU - Lin, Yuan
AU - Padua, David
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2000.
PY - 2000
Y1 - 2000
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84956992147&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84956992147&partnerID=8YFLogxK
U2 - 10.1007/3-540-46423-9_14
DO - 10.1007/3-540-46423-9_14
M3 - Conference contribution
AN - SCOPUS:84956992147
SN - 354067263X
SN - 9783540672630
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 202
EP - 218
BT - Compiler Construction - 9th International Conference, CC 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000, Proceedings
A2 - Watt, David A.
PB - Springer
T2 - 9th International Conference on Compiler Construction, CC 2000 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2000
Y2 - 25 March 2000 through 2 April 2000
ER -