A Two-step Approach to Find Short Compilation Transformation Sequences for Optimal Software Runtime Performance

Abstract

More efficient programs can be obtained by applying compiler optimization flags, i.e., sequences of code transformations. However, these generic sequences often underperform, as their effectiveness depends on both the software and hardware characteristics. This highlights the need for tailored transformation sequences. This paper introduces a new problem composed of two combinatorial optimization tasks aimed at finding optimal and minimal-length source code transformation sequences. Shorter sequences enable faster compilation using only the most effective transformations for a given program and hardware. We propose a two-step methodology to solve the problem: first, find sequences that minimize program runtime; second, reduce their length without degrading performance. Our approach produces sequences up to 51.27% shorter and over 26% faster compared to the -O3 flag.