next up previous
Next: Array Reductions. Up: Array Analysis Previous: Summaries.

Array Data-Flow Analysis.

A single array data-flow analysis is used to determine arrays involved in data dependences, to locate privatizable arrays and to recognize reductions. Array data-flow analysis is a bottom-up interprocedural analysis on the loops and procedures of the program, using the region-based analysis framework described above. The analysis computes the following four sets of summaries for each program region: the array sections that are definitely written ( MustWrite), that may be written ( Write), that may be read ( Read), and that may be read before they are written ( ExposedRead).

Data dependence testing at a loop is a comparison of the Read and Write sets to determine if they are disjoint for different iterations of the loop. Some arrays involved in data dependences may yield to privatization. An array can be privatized if the Write set and the ExposedRead set from different iterations are disjoint. Our array privatization analysis is an extension of Tu and Padua's approach [26]. Their algorithm requires that a privatizable array have no read locations upwards-exposed to the beginning of a loop iteration. Our approach is more general, capturing cases such as the one in Figure 2(c).

Saman Amarasinghe
Fri Sep 15 09:15:06 PDT 1995