Loop Nest Optimizer - GNU Project - Free Software Foundation (FSF)

Passes in the branch

The analysis of scalars evolutions

This pass analyzes the evolution function of scalar variables. It is based on the SSA and the loop hierarchy representations of the program. The aim of the pass is to compute when possible an approximation of the number of iterations of the natural loops. A first design document describes the SSA based algorithm that has been implemented.

The analysis of data dependences

The scalar evolution analyzer computes the data access functions. Based on the evolution functions of two conflicting array accesses, the data dependence testers try to determine the elements that access the same memory location: the conflicting elements. The classic distance and direction vectors are abstracted from the representation of the conflicting elements.

Vectorization

This pass should vectorize certain loops, using classic data dependence based approach.

Next passes

Elimination of redundant checks

Based on the scalar evolutions informations, it is sometimes possible to extend the range of action of the constant copy propagation after the loop structures. Given an iteration domain, it is possible to detect redundant checks that are sometimes introduced automatically by the compiler (as in -fbounds-check).

Temporal and spatial locality of data references

This pass builds a geometrical representation of the order in which data sets are accessed. It transforms the loop iterations in order to keep the data references in caches. The algorithm is described in these papers. A more general framework for loop nests transformations has been proposed using the same high level polyhedral representation: WRaP-IT.

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

These pages are maintained by the GCC team.

For questions related to the use of GCC, please consult these web pages and the GCC manuals. If that fails, the gcc-help@gcc.gnu.org mailing list might help.
Please send comments on these web pages and the development of GCC to our developer mailing list at gcc@gnu.org or gcc@gcc.gnu.org. All of our lists have public archives.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Last modified 2006-06-21