next up previous
Next: Representation: Summaries Up: Interprocedural Analysis for Parallelization Previous: Live Variable Analysis.

Analysis of Array Variables

  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.

Saman Amarasinghe
Mon Oct 2 11:00:22 PDT 1995