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 (TOPLAS). 24 (1): 65–109. doi:10.1145/509705.509708.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

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