Kavli Affiliate: Ke Wang
| First 5 Authors: Yu Wang, Hongyu Chen, Ke Wang, ,
| Summary:
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.
| Search Query: ArXiv Query: search_query=au:”Ke Wang”&id_list=&start=0&max_results=3