A practical algorithm for exact array dependence analysis
William White Tison 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]