If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? We'll assume that inline assembly and similar features are not used. If this is not always possible, (and I suspect it probably isn't) what language features or particular types of compiler optimizations make "fully pre-optimized" source code impossible?
The key to remember is that, at its core, a compiler is just a translator between two languages. One is often machine code, and there may be some intermediate steps, but translation is the key.
With that in mind, an optimization is one of three things:
A transformation from source programs to source programs, that is (hopefully) observationally equivalent to the original program, that is (hopefully) faster
A transformation from source programs to target that takes advantage of some property of the source program to generate code that is equivalent to, but faster than, the "vanilla" compiled version of the code.
A transformation from target programs to target programs that produces equivalent but faster code.
(3) could happen after compilation, since it doesn't rely on source input at all, and (1) could happen in an interpreted language as much as a compiled one.
Naturally, (2) can encompass programs that can't necessarily be expressed in the source language. It all depends the properties of your transformation. Is it a surjection between your source and target languages?
If it's not surjective, and both languages are Turing Complete, then:
- There must be some programs in the target language which are never the result of compilation
- Each "unreached" target program is equivalent to some source program (since both languages are Turing Complete)
Some of these will likely be optimizations.
For some practical examples:
- Tail-call elimination is not expressible as a source-to-source transformation in any language with higher-order functions lacking GOTO
- Any optimization using a "special" CPU instruction can't be expressed as a source-to-source transformation, since there's no way to access that instruction from the source language.
There are likely many more. (Community: feel free to add examples as you see fit!)