Array-access analysis

In computer science, array-access analysis is a compiler analysis approach used to decide the read and write access patterns to elements or portions of arrays.^[1]

The major data type manipulated in scientific programs is the array. The define/use analysis on a whole array is insufficient for aggressive compiler optimizations such as auto parallelization and array privatization. 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, 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

^ Paek, Yunheung; Hoeflinger, Jay; Padua, David (January 2002). "Efficient and precise array access analysis". ACM Transactions on Programming Languages and Systems. 24 (1): 65–109. doi:10.1145/509705.509708.

This programming-language-related article is a stub. You can help Wikipedia by expanding it.

[Paek2002-1] Paek, Yunheung; Hoeflinger, Jay; Padua, David (January 2002). "Efficient and precise array access analysis". ACM Transactions on Programming Languages and Systems. 24 (1): 65–109. doi:10.1145/509705.509708.

[1]

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Array-access analysis

References

Wikious

Boobota

Sagapedia