Joint scheduling and layout optimization to enable multi-level vectorization

We describe a novel loop nest scheduling strategy imple-mented in the R-Stream compiler1: the first scheduling for-mulation to jointly optimize a trade-off between parallelism, locality, contiguity of array accesses and data layout permu-tations in a single complete formulation. Our search space contains the maximal amount of vectorization in the pro-gram and automatically finds opportunities for automatic multi-level vectorization and simd-ization. Using our model of memory layout, we demonstrate that the amount of con-tiguous accesses, vectorization and simd-ization can be in-creased modulo data layout permutations automatically ex-posed by our technique. This additional degree of freedom opens new opportunities for the scheduler that were previ-ously out of reach. But perhaps the most significant aspect of this work is to encompass an ever increasing number of traditional optimization phases into a single pass. Our ap-proach offers a good solution to the fundamental problem of phase ordering of high-level loop transformations. 1