Loop nest optimization is a combinatorial problem. Its involves two increasingly difficult tasks, considering the growing complexity of modern architectures:
- the profitability analysis of transformation sequences to enhance parallelism, locality, and resource usage, which amounts to a hard inverse problem on a non-linear objective function;
- the construction and exploration of search space of transformation sequences, whose legality is unpredictable and costly.
Practical optimizing and parallelizing compilers decouple these tasks, resorting to a predefined set of enabling transformations to eliminate all sorts of optimization-limitating semantical constraints. State-of-the-art optimization heuristics face a hard decision problem on the selection of enabling transformations (only remotely related to performance).
We propose an alternative design where optimization heuristics first address the main performance anomalies, then correct potentially illegal loop transformations a posteriori, attempting to minimize the performance impact of the necessary adjustments.
We propose a general method to correct any sequence of loop transformations through a combination of loop shifting, code motion and index-set splitting. Sequences of transformations are modeled by compositions of geometric transformations on multidimensional affine schedules. We provide experimental evidence of the effectiveness and scalability of the algorithms on real loop optimization problems.