PIT: A Framework for Effectively Composing High-Level Loop Transformations

Abstract

The increasing complexity of modern architectures and memory models challenges the design of optimizing compilers. It is mandatory to perform several optimizing transformations of the original program to exploit the machine to its best, especially for scientific, computational-intensive codes. Aiming at investigating the best transformation sequence and the best transformation parameters simultaneously, this paper presents a novel loop transformation framework, which integrates the advantages of polyhedral model and model-guided iterative compilation to create a powerful framework that is capable of fully automated non-parametric transformations and model-guided parametric transformations as well as automatic parameter search. The framework employs polyhedral model to facilitate the search of non-parametric code transformation composition, and designs a transformation model based on hardware performance counters to guide when, where and in what order to apply transformations to get the most benefit, finally uses Nelder-Mead simplex algorithm to find the optimal parameters. The framework is demonstrated on three typical computational kernels for code transformations to achieve performance that greatly exceeds the native compiler, and is significantly better than state-of-the-art polyhedral model based loop transformations and iterative compilation, generating efficient code on complex loop nests.