Loop Nest Optimizer
This project aims at implementing a loop nest optimizer at the tree
level.
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 in
the WRaP-IT project.