Efficient and precise array access analysis

Yunheung Paek, Jay Hoeflinger, David Padua

Research output: Contribution to journalArticlepeer-review

Abstract

A number of existing compiler techniques hinge on the analysis of array accesses in a program. The most important task in array access analysis is to collect the information about array accesses of interest and summarize it in some standard form. Traditional forms used in array access analysis are sensitive to the complexity of array subscripts; that is, they are usually quite accurate and efficient for simple array subscripting expressions, but lose accuracy or require potentially expensive algorithms for complex subscripts. Our study has revealed that in many programs, particularly numerical applications, many access patterns are simple in nature even when the subscripting expressions are complex. Based on this analysis, we have developed a new, general array region representational form, called the linear memory access descriptor (LMAD). The key idea of the LMAD is to relate all memory accesses to the linear machine memory rather than to the shape of the logical data structures of a programming language. This form helps us expose the simplicity of the actual patterns of array accesses in memory, which may be hidden by complex array subscript expressions. Our recent experimental studies show that our new representation simplifies array access analysis and, thus, enables efficient and accurate compiler analysis.

Original languageEnglish (US)
Pages (from-to)65-109
Number of pages45
JournalACM Transactions on Programming Languages and Systems
Volume24
Issue number1
DOIs
StatePublished - Jan 1 2002

Keywords

  • Algorithms
  • Array access analysis
  • D.3.4 [Programming Languages]: Processors - compilers, optimization
  • F.3.2 [Logics and Meanings of Programs]: Semantics of Programming Languages - program analysis
  • Internal representation
  • Languages

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Efficient and precise array access analysis'. Together they form a unique fingerprint.

Cite this