transformations for improving data access locality in non-perfectly nested loops
Loop transformation techniques have matured to the point where the techniques are well integrated into production optimizing compilers~\cite{kaixpert:97}. However, we believe that new and aggressive techniques are necessary because: computer system manufacturers have announced their plans for forthcoming processors with over 1GHz clock frequency, wherein the miss penalties can be very high, and transformation techniques have saturated in that they have delivered majority of the benefit that can be obtained with perfectly nested loops. The new techniques must target improvement of coverage, that is the classes of loops that can be optimized for locality of data access.In this paper, we present a new technique called size-reduction transformation to improve data access locality in a class of non-perfectly nested loops. The new technique is very effective, when existing techniques, namely, linear loop and array transformations, fail to improve locality of reference. Size-reduction transformations are implemented in IBM's Fortran 90 optimizing compiler released recently, and have contributed significantly to the high performance of the compiler.
optimizing compiler size-reduction transformations locality of reference performance loop and data transformations