A practical algorithm for exact array dependence analysis
William Pugh · Communications of the ACM · 1992
ndamental analis step in an ad-',nced optimizing compiler (as well as many other software tools) is data dependence analysis for arrays.This means deciding if two references to an array can refer to the same element and if so, under what conditions.This information is used to determine allowable program transformations and optimizations.For example, we can determine that in the following code fragment, no location of the array is both read and written.Once we also verify that no location is written more than once, we know that the writes can be done in any order.for i= 1 to 100 do forj --i to 100 do A [i, j+ 11 = A[100,j]
Cited by 568 works. doi:10.1145/135226.135233 Open-access PDF
Authors
References
- Optimizing supercompilers for supercomputers
- Automatic translation of FORTRAN programs to vector form
- Parallelism exposure and exploitation in programs
- On the Number of Operations Simultaneously Executable in Fortran-Like Programs and Their Resulting Speedup
- Dependence Analysis for Supercomputing
- Dependence analysis for subscripted variables and its application to program transformations
- Interprocedural dependence analysis and parallelization
- Deciding Linear Inequalities by Computing Loop Residues
- Efficient and exact data dependence analysis
- Fourier-Motzkin elimination and its dual