Categories and Subject Descriptors

We 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 gen-erated program P ′ is “optimal ” ? We prove in this article that this problem is undecidable in two general schemes of optimizing com-pilation: 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 sequenc