The array analysis
locates loops
that carry no data dependences on array elements
or
that can be safely parallelized
after array privatization.
The system,
when integrated
with the reduction recognition and scalar data-flow
analysis,
performs an array data-flow analysis based on systems
of linear inequalities to
analyze affine array access functions. This approach is
driven by the need to
compute both data dependences and value-based dependences for
array privatization in a framework that is suitable for
flow-sensitive interprocedural analysis.
An important feature of the array data-flow analysis is the
use of summaries, which describe subarrays accessed by a region of
the code; summaries eliminate the need to perform
pairwise dependence
tests for a loop containing n array accesses.
This efficiency consideration may be unimportant within a single
procedure, but is crucial when analyzing large loops that may span multiple
procedures and have hundreds of array accesses.