computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

, array-access analysis is a compiler analysis approach used to decide the read and write access patterns to elements or portions of arrays. The major data type manipulated in scientific programs is the array. The define/use analysis on a whole array is insufficient for aggressive

compiler optimization An optimizing compiler is a compiler designed to generate code that is optimized in aspects such as minimizing program execution time, memory usage, storage size, and power consumption. Optimization is generally implemented as a sequence of op ...

s such as auto parallelization and array

privatization Privatization (rendered privatisation in British English) can mean several different things, most commonly referring to moving something from the public sector into the private sector. It is also sometimes used as a synonym for deregulation w ...

. Array access analysis aims to obtain the knowledge of which portions or even which elements of the array are accessed by a given code segment (

basic block In compiler construction, a basic block is a straight-line code sequence with no branches in except to the entry and no branches out except at the exit. This restricted form makes a basic block highly amenable to analysis. Compilers usually decom ...

, loop, or even at the procedure level). Array-access analysis can be largely categorized into exact (or reference-list-based) and summary methods for different tradeoffs of accuracy and complexity. Exact methods are precise but very costly in terms of computation and space storage, while summary methods are approximate but can be computed quickly and economically. Typical exact array-access analysis include linearization and atom images. Summary methods can be further divided into array sections, bounded regular sections using triplet notation, linear-constraint methods such as data-access descriptors and array-region analysis.

References

Compiler construction Static program analysis {{prog-lang-stub