Non-affine extensions to polyhedral code generation

This paper describes a loop transformation framework that extends a polyhedral representation of loop nests to rep- resent and transform computations with non-affine index arrays in loop bounds and subscripts via a new interface between compile-time and run-time abstractions. Polyhe- dra scanning code generation, which historically applies an affine mapping to the subscript expressions of the statements in a loop nest, is modified to apply non-affine mappings in- volving index arrays that are represented at compile time by uninterpreted functions; non-affne loop bounds involv- ing index arrays are also represented. When appropriate, an inspector is utilized to capture the non-affine subscript mappings, and a generalized loop coalescing transformation is introduced as a non-affine transformation to support non- Affine loop bounds. With this support, complex sequences of new and existing transformations can then be composed. We demonstrate the effectiveness of this framework by optimiz- ing sparse matrix vector multiplication operations target- ing GPUs for different matrix structures and parallelization strategies.This approach achieves performance that is com- parable to or greater than the hand-tuned CUSP library; for two of the implementations it achieves an average 1.14× im- provement over CUSP across a collection of sparse matrices, while the third performs on average within 8% of CUSP.