On the decidability of phase ordering problem in optimizing compilation
- 3 May 2006
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM) in Proceedings of the 3rd conference on Computing frontiers - CF '06
Abstract
International audienceWe are interested in the computing frontier around an essential question about compiler construction: having a program P and a set M of non parametric compiler optimization modules (called also phases), is it possible to find a sequence s of these phases such that the performance (execution time for instance) of the final generated program P′ is "optimal" ? We prove in this article that this problem is undecidable in two general schemes of optimizing compilation: iterative compilation and library optimization/generation. Fortunately, we give some simplified cases when this problem be-comes decidable, and we provide some algorithms (not necessary efficient) that can answer our main question. Another essential question that we are interested in is parame-ters space exploration in optimizing compilation (tuning optimizing compilation parameters). In this case, we assume a fixed sequence of optimization, but each optimization phase is allowed to have a parameter. We try to figure out how to compute the best parameter values for all program transformations when the compilation sequence is given. We also prove that this general problem is undecidable and we provide some simplified decidable instancesKeywords
This publication has 15 references indexed in Scilit:
- Elimination of quantifiers from arithmetical formulas defining recursively enumerable setsMathematics and Computers in Simulation, 2004
- A Polyhedral Approach to Ease the Composition of Program TransformationsLecture Notes in Computer Science, 2004
- Automated empirical optimizations of software and the ATLAS projectParallel Computing, 2001
- An approach for exploring code improving transformationsACM Transactions on Programming Languages and Systems, 1997
- Combining analyses, combining optimizationsACM Transactions on Programming Languages and Systems, 1995
- Precise compile-time performance prediction for superscalar-based computersACM SIGPLAN Notices, 1994
- Approaching a machine-application bound in delivered performance on scientific codeProceedings of the IEEE, 1993
- On optimal parallelization of arbitrary loopsJournal of Parallel and Distributed Computing, 1991
- Estimating interlock and improving balance for pipelined architecturesJournal of Parallel and Distributed Computing, 1988
- Universal diophantine equationThe Journal of Symbolic Logic, 1982