# Beyond the Phase Ordering Problem: Finding the Globally Optimal Code w.r.t. Optimization Phases

arXiv: https://arxiv.org/abs/2410.03120 · HTML: https://mlsanity.com/paper/2410.03120/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Oct 2024.

## Built on by (most cited first, 1 of 1)

- [MQSS-Selector: RL-Guided Pass Selection for an MLIR Compilation Pipeline](https://mlsanity.com/paper/2609.30104/) (2026)

## Abstract (arXiv)

In this paper, we propose a new concept called textitsemantically equivalence wrt textitoptimization phases textit(sep), which defines the set of programs a compiler considers semantically equivalent to the input using a set of optimization phases. We show both theoretically and empirically that solving the phase ordering problem does not necessarily result in the most efficient code among all programs that a compiler deems semantically equivalent to the input, hereinafter referred to as the global optimal code wrt optimization phases. To find the global optimal code wrt optimization phases, we present a conceptual framework, leveraging the reverse of existing optimization phases. In theory, we prove that the framework is capable of finding the global optimal code for any program. We realize this framework into a technique, called textititerative bi-directional optimization (tool), which performs both the normal and reverse optimizations to increase and decrease the efficiency of the generated code, respectively. We evaluate tool on C/C++ files randomly extracted from highly mature and influential programs (eg, Linux kernel, OpenSSL, Z3). Results show that tool frequently generates more efficient code -- measured by either code size or runtime performance -- than exhaustive search, which is the solution to the phase ordering problem. We also find by simply incorporating tool's reverse optimization phases, the effectiveness of the optimization of state-of-the-art compilers (eg, GCC/LLVM) can be significantly improved.