Path: csiph.com!weretis.net!feeder9.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From: John R Levine <johnl@taugh.com>
Newsgroups: comp.compilers
Subject: draft: Optimal phase ordering doesn't produce optimal code
Date: Mon, 07 Oct 2024 17:16:39 -0400
Organization: Compilers Central
Sender: johnl%iecc.com
Approved: comp.compilers@iecc.com
Message-ID: <24-10-002@comp.compilers>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="92127"; mail-complaints-to="abuse@iecc.com"
Keywords: optimize
Posted-Date: 07 Oct 2024 17:17:09 EDT
X-submission-address: compilers@iecc.com
X-moderator-address: compilers-request@iecc.com
X-FAQ-and-archives: http://compilers.iecc.com
Xref: csiph.com comp.compilers:3601

This paper starts with an example where the best ordering of optimizations
doesn't produce optimal code because there are better results that involve
intermediate steps that make worse code.  They propose a new ordering that
works better.

Solving the Phase Ordering Problem ≠ Generating the Globally Optimal Code

Yu Wang, Hongyu Chen, Ke Wang

Phase ordering problem has been a long-standing challenge in compiler
optimizations. Over the past four decades, a significant amount of effort
has been devoted, and indeed, substantial progress has been made. However,
in this paper, we raise questions about the overall significance of
solving the phase ordering problem in the first place, as pursuing a
solution to this problem may not align with the fundamental goal of
compiler optimizations, \ie, generating the globally optimal code among
all programs that compilers deem semantically equivalent to an input
program.

Our findings, supported by both theoretical and empirical evidence, show
that solving the phase ordering problem is not equivalent to generating
such globally optimal code. The fundamental reason that applying the
optimal phase ordering may still result in suboptimal code is the
exclusion of programs of less efficiency during the optimization process.
Motivated by this insight, we propose a theoretical approach, called
\textit{infinitive iterative bi-directional optimizations}
(\textit{IIBO}), which is guaranteed to converge to the globally optimal
code for any input program. We realize IIBO into a practical algorithm and
apply it to optimize real-world programs. Results show that IIBO
frequently generates more efficient code than GCC/LLVM, two
state-of-the-art industry compilers, as well as exhaustive search, which
can be deemed the solution to the phasing ordering problem.% input
programs.

Given the significance and impact of our results, we are currently in
active discussions with LLVM engineers on the possible incorporation of
our findings into their next release. In general, we expect our work to
inspire new design principles for compiler development in the pursuit of
generating the globally optimal code.


https://arxiv.org/abs/2410.03120

Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly