INTERPROCEDURAL ARRAY REGION ANALYSES

Many program optimizations require exact knowledge of the sets of arra y elements that are referenced in or that flow between statements or p rocedures. Some examples are array privatization, generation of commun ications in distributed memory machines, or compile-time optimization of cache behavior in hierarchical memory machines. Exact array region analysis is introduced in this article. These regions exactly represen t the effects of statements and procedures upon array variables. To re present the flow of these data, we also introduce two new types of arr ay region analyses: IN and OUT regions. The intraprocedural propagatio n is presented, as well as a general linear framework for interprocedu ral analyses, which handles array reshapes. The intra- and inter-proce dural propagation of array regions is implemented in PIPS, the interpr ocedural parallelizer of FORTRAN programs developed at Ecole des mines de Paris.