1
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ Many things that are considered "optimizations" simply don't operate at the level of source code. For example, register allocation and stack frame layout. Source-level languages rarely presume let alone require that you are targeting a register-based machine so there can't be anything more than an advisory mechanism to say anything about register allocation. At any rate, "no optimizations" is not a well-defined general notion. Even with optimizations "disabled" the compiler and run-time are still making decisions. $\endgroup$ – Derek Elkins Jul 21 '17 at 3:43
3
$\begingroup$

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:

  1. A transformation from source programs to source programs, that is (hopefully) observationally equivalent to the original program, that is (hopefully) faster

  2. 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.

  3. 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!)

$\endgroup$
  • $\begingroup$ Source to source, source to target, target to target. I wonder if I would be useful to have target to source transformations. That is, suggestions from the compiler of ways the source code could be made closer to the final optimized target. Since applying those transformations would presumably speed up compilation, (fewer source to source transformations would be needed,) they could be thought of as optimizations to future compilations of the program. $\endgroup$ – Ryan1729 Jul 22 '17 at 7:23
  • $\begingroup$ @Ryan1729 Maybe, but I doubt it. If a compiler can detect an optimization it usually makes sense to apply it without asking the user to change their code. Source Code is meant to be read, and Machine code to be run. The point of an optimization is to allow the programmer to write their code in a simple, straightforward way that's easy to understand and maintain, while getting the performance an optimized version would read. The goal is to have as many optimizations in the target and as few in the source as is possible. $\endgroup$ – jmite Jul 22 '17 at 8:20
  • $\begingroup$ The event that prompted this question was a library I'm using performs very slowly in the compiler's unoptimized debug mode, but with acceptable performance in release mode. This makes running the program in debug mode (mostly for faster compile times,) a bit of a chore. So if the compiler could suggest an optimized version of the source code, that would be helpful in at least that case. I could also see these kind of messages about how the compiler transforms a particular piece of code being useful in a pedagogical setting. But those use cases are admittedly far from the general case. $\endgroup$ – Ryan1729 Jul 22 '17 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.