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

1 INTRODUCTION

• In the example, LLVM’s optimally ordered output Pb is less efficient than equivalent Pc, which uses fewer instructions and is estimated to run faster.LLVM machine-code analysis estimates Pc nearly four times faster on X86 and 10% faster on RISC-V; LLVM and GCC produce four fewer X86 instructions and two fewer RISC-V instructions for Pc.Source: §1 · p. 2
• The phase-ordering problem can miss better code because its efficiency-improving passes do not explore less efficient intermediate programs that may lead to a better result.The example’s Pc can be reached by optimizing Pd, which is less efficient than the input Pa.Source: §1 · p. 3, Figure 2 · p. 3
• The conceptual framework reverses selected optimization passes so compilers can explore both more- and less-efficient programs within the phase-defined equivalence set.The framework is theoretically capable of finding the global optimum, but identifying a minimum useful set of passes to reverse remains key.Source: §1 · p. 4
• IBO produces more efficient code than exhaustive search for 20 of 50 files after two iterations, and outperforms GCC or LLVM for more than half of 200 files after three iterations.The comparisons use code size or runtime performance; the compiler comparison uses each compiler’s -O3 mode.Source: §1 · pp. 4–5
• IBO applies reverse passes to generate less efficient programs, then optimizes each generated program using optimal phase ordering; finite iterations may yield only a local optimum.For GCC/LLVM comparisons, IBO applies reverse optimizations and then directly compiles each generated program with the corresponding compiler.Source: §1 · pp. 4–5
• The authors formalize semantic equivalence w.r.t. optimization phases and show optimal pass ordering need not find the most efficient program in that equivalence set.The paper defines the globally optimal code as the most efficient code among programs a compiler deems equivalent to its input.Source: §1 · pp. 2, 5

2.1 Preliminary

• Cop models a compiler’s optimization component: it applies a set of optimization phases to source-language programs.Each phase consists of a sequence of semantically preserving program transformations.Source: §2.1 · p. 5
• Combining the transformations from all phases gives the complete transformation set T used by Cop.The set representation ignores sequence order and removes duplicate transformations.Source: §2.1 · p. 5
• Each transformation maps a program in language L to another program, and a phase applies its transformations successively.Multiple phases are likewise applied in sequence to the program.Source: §2.1 · pp. 5–6
• Efficiency is represented by δ, with larger values indicating more efficient programs; the paper uses code size and runtime performance as its measures.Source: §2.1 · p. 6
• The phase-ordering problem seeks a pass ordering whose application to the input produces code more efficient than any other ordering.Source: §2.1 · p. 6

2.2 Semantic Equivalence w.r.t. Optimization Phases

• SEP defines two programs as equivalent relative to Φ when one can be transformed into the other, or vice versa, by an optimization pass in Φ.Source: §2.2 · p. 6
• Because SEP is transitive, its definition extends to programs connected by a sequence of passes from Φ.Source: §2.2 · p. 6
• The programs equivalent to P under Φ form the set P = {P′ | P′ Φ≡ P}.Source: §2.2 · p. 6

3.1 Defining the Problem of Finding the Global Optimum w.r.t. Optimization Phases

• The global optimum is the most efficient program among all programs semantically equivalent to the input w.r.t. the given optimization passes.It always exists for code-size efficiency; when runtime also matters, existence requires a bounded code size.Source: §3.1 · pp. 6–7

3.2 Solving the Phase Ordering Problem

• An optimal ordering of passes can fail to produce the global optimum because a different, semantically equivalent starting program can optimize to more efficient code.The paper’s LEBO argument establishes that some program pairs yield different outputs under their respective optimal orderings.Source: §3.2 · pp. 7–8

3.3 The Relationship between the Problem of Finding the Globally Optimal Code w.r.t. Optimization Phases and the Phase Ordering Problem

• Global-optimum finding generalizes phase ordering: it seeks an equivalent starting program whose optimal ordering produces the global optimum.The two problems coincide when the relevant starting program can be obtained by optimizing the input; otherwise, it must be found first.Source: §3.3 · pp. 8–9
• The paper argues that global optimization could make generated performance less sensitive to developers’ code style choices.It connects this consequence to style guidelines that prioritize readability and maintainability but may not align with compiler optimization.Source: §3.3 · p. 9

3.4 (Un)Decidability of the Problem of Finding the Globally Optimal Code

• Finding the globally optimal code w.r.t. optimization phases is undecidable.The proof reduces the halting problem to global-optimum finding.Source: §3.4 · p. 9

• The reduction adds code independent of the halting program and sets var2 from π, making the added code’s global optimum depend on whether the program halts.If it halts, the code can be optimized to a form at least as efficient as printf("%d",(var1/10) * 6 + var1); otherwise, its optimum is less efficient than that form.Source: Step (1): construct a specific program · pp. 9–10
• The problem of finding the globally optimal code is NP-hard.The section states this result after its undecidability proof.Source: Step (1): construct a specific program · p. 10
• A property π is created by instrumenting the halting program so it is true if and only if the program halts on the given input.The construction assigns true at a program point reached exactly when the halting program terminates.Source: Step (1): construct a specific program · pp. 9–10

4.1 A Conceptual Framework Based on Reverse Optimizations

• Adding the reverse of every optimization pass lets the compiler explore all programs semantically equivalent under the original passes and find the global optimum.The theorem assumes each original pass strictly increases code efficiency; each reverse pass undoes its corresponding optimization.Source: §4.1 · p. 11
• The framework’s practical challenge is selecting useful passes to reverse; some reversals, such as inserting dead code or extracting inlined functions, do not help find the optimum.The minimum set of optimization passes to reverse is defined as the smallest subset whose reversals, together with forward passes, can transform the input into the global optimum.Source: §4.1 · p. 11

4.2 A Method for Realizing the Conceptual Framework

• IBO alternates reversing selected passes to generate less efficient programs and applying an optimal ordering of all passes to each generated program.Across iterations, it retains the most efficient program found so far.Source: §4.2 · pp. 12–13
• IBO is not guaranteed to find the global optimum: its finite iterations may miss equivalent programs, and its selected reversals may omit passes in the minimum set.It may therefore discover only a local optimum.Source: §4.2 · p. 13

5.1 The Implementation of Iterative Bi-Directional Optimizations

• IBO selects reversals for influentiality, diversity, and simplicity, prioritizing transformations that enable different optimization sequences while avoiding complex reversals such as dynamic loop unrolling.The implementation runs in LLVM’s IR infrastructure and applies reverse transformations before optimizing generated programs.Source: §5.1 · pp. 13–14

5.2.1 Comparing IBO with Exhaustive Search.

• The exhaustive-search comparison samples 50 single-function files of at most 100 lines from 12 influential programs and searches sequences of LLVM -O3 passes, excluding inter-procedural passes.For selecting code, the study compiles whole programs and chooses the executable with the fastest average runtime across test suites and target architectures.Source: §5.2.1 · pp. 14–16
• With one iteration, IBO generates IR with 25%+ fewer instructions and code that runs 20%+ faster than exhaustive search; the margin increases with two iterations.IBO’s compile time is significantly longer, and the number of programs explored grows exponentially with reverse-optimization steps and exhaustive search.Source: Table 2 · p. 16, §5.2.1 · pp. 16–17

5.2.2 Improving the Optimizations of State-of-The-Art Compilers.

• The implementation’s finite iterations cannot explore the entire semantically equivalent program set, while its compilation cost grows substantially in the evaluated comparisons.The paper identifies more efficient identification of the minimum set of reversals as a direction for addressing the cost.Source: §5.2.1 · p. 16, §5.2.2 · pp. 19–20

5.2.1 Comparing IBO with Exhaustive Search.

• In the QEMU example, reversing InstCombine lets IBO expose equivalent conditions and remove a redundant if clause that exhaustive search cannot eliminate.The qualitative study reports that IBO’s improved efficiency generally comes from fewer, more efficient instructions or simplified control-flow structures.Source: §5.2.1 · pp. 17–18

5.2.2 Improving the Optimizations of State-of-The-Art Compilers.

• At k=5, IBO code runs 20%+ faster than LLVM and over 30%+ faster than GCC, with instruction count close to half of either compiler’s.At k=3, IBO produces more efficient code than GCC/LLVM for more than half of the files; its compile time is much longer.Source: Table 3 · p. 19, §5.2.2 · p. 19

6.1 The Phase Ordering Problem

• Phase-ordering work ranges from flexible compiler designs and interactive tuning to iterative search, expert-built pass-interaction graphs, Bayesian optimization, and machine-learning methods.Examples include exhaustive evaluation [Kulkarni et al. 2006, 2009], BaCO [Hellsten et al. 2023], MiCOMP, and Autophase.Source: §6.1 · p. 20

6.2 Superoptimization

• Superoptimization searches for efficient instruction sequences within a specific ISA, whereas this paper addresses phase ordering’s limited transformations rather than an ISA-level global optimum.Examples include stochastic search in STOKE, synthesis in Souper [Sasnauskas et al. 2017], and constraint-based methods in SuperStack.Source: §6.2 · p. 20

7 CONCLUSION

• The framework aims to find globally optimal code by using reverse optimization passes to explore programs a compiler deems equivalent to its input.The authors state that, in theory, the framework can find globally optimal code for any program.Source: §7 · p. 20
• IBO frequently generates more efficient code than exhaustive search and outperforms GCC and LLVM by incorporating reverse optimizations.The authors present IBO as a preliminary realization of the framework.Source: §7 · p. 21
• Identifying the minimum set of optimizations to reverse is the key challenge for finding globally optimal code.The authors describe formulating a policy for using these reversals as future work.Source: §7 · p. 21