Facilitating the Exploration of Compositions of Program Transformations

Static cost models have a hard time coping with hardware components exhibiting complex run-time behaviors, calling for alternative solutions. Iterative optimization is emerging as a promising research direction, but currently, it is mostly limited to finding the parameters of program transformations. We want to extend the scope and efficiency of iterative optimization techniques by searching not only for the appropriate parameters of a given transformation, but for the program transformations themselves, and especially for compositions of program transformations. The purpose of this article is to introduce a framework for easily expressing compositions of program transformations. This framework relies on a unified polyhedral representation of loops and statements. The key is to clearly separate the impact of each program transformation on the following three components: the iteration domain, the schedule and the memory access functions. We show that, within this framework, composing a long sequence of program transformations induces no code size explosion. As a result, searching for compositions of transformations is not hampered by the multiplicity of compositions, and in many cases, it is equivalent to testing different values for the coefficients of the representation matrices. Our techniques have been implemented on top of the Open64/ORC compiler