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.