Non-unimodular transformations of nested loops

A linear algebraic approach to modeling loop transformations is presented which unifies apparently unrelated recent developments in supercompiler technology. The relationship between the dependence abstraction called dependence cones and fully permutable loop nests is shown. Compound transformations are modeled as matrices. Nonsingular linear transformations that subsume the class of unimodular transformations are presented. Nonunimodular transformations (with determinant⩾1) create `holes´ in the transformed iteration space. The step size of loops is changed in order to `step aside from these holes´ when traversing the transformed iteration space. For the class of nonunimodular loop transformations, algorithms for deriving the loop bounds, the array access expressions, and step sizes of loops in the nest are given. The algorithms are based on the Hermite normal form of the transformation matrix. The use of this approach in several problems such as generation of tile sets, distributed memory code generation, and dependence analysis