Non-unimodular transformations of nested loops
Jagannathan Ramanujam · 1992
This paper presents a linear algebraic approach to modeling loop transformations. The approach unifies apparently unrelated recent developments in supercompiler technology. Specifically we show the relationship between the dependence abstraction called dependence cones, and fully permutable loop nests. Compound transformations are modeled as matrices. Nonsingular linear transformations presented here subsumes the class of unimodular transformations. Nonunimodular transformations (with determinant 1) create "holes" in the transformed iteration space. We change the step size of loops in order to "step aside from these holes" when traversing the transformed iteration space. For the class of non-unimodular loop transformations, we present algorithms for deriving the loop bounds, the array access expressions and step sizes of loops in the nest. The algorithms are based on the Hermite Normal Form of the transformation matrix. We illustrate the use of this approach in several problems such a...