It is today widely accepted that good programming languages should have clean semantics. Semantics usually define the values programs compute, or fail to compute. However this is insufficient: what good is a correct value if the program that computes it takes forever to terminate, or consumes too much memory?
A good programming language should also guarantee the complexity of its basic constructs. It should be possible for the programmer to usefully predict the performance of his program without depending on compiler internals. Compiler optimizations that may alter the asymptotic performance of programs should be documented as well as the value semantics of the language. For instance, most functional language guarantee tail-call optimization, and this is good. Tail-calls are easy to spot for the programmer; it is easy to conceptualize what happens when a call is tail and when it is not (e.g., call chain proportional to the number of calls).
I'm tempted to consider that compilers that perform optimizations potentially changing the asymptotic performance or substantially changing the actual performance of programs are incorrect, when those optimizations are not mandated by the language definition. Why? Because programmers will rely on them. However, compiler optimizations are tricky beasts that do not always apply or work the same way. A new way of compiling may yield much better performance than the old one, save in a few cases. If "better" here means "asymptotically better" and if the performance of your program was depending, by chance, on those corner cases (how would you know without delving in the internals of complex optimizations?), your program may go from O(n) to O(n^2) and fail.
That will then create compiler-specific subdialects of the language. The maintainers of the compiler will have to ensure that these optimizations always apply in all future versions of the compiler. This is no better than backwards bug-compatibility or browser-specific hacks. This means that they won't be able to change their optimization strategy if it is not formally a superset of the previous one, even if it performs better in almost all known programs.
You will then end up with programs P1 and P2 written in the same language, but such that P1 has usable perfomance only when compiled with flags F1, with which P2 hasn't usable performance. Usually you can't mix compilation flags, so you won't be able to compose programs P1 and P2 in a bigger program and have acceptable performance.
Whole-program compilers that optimize the hell out of your programs are a good thing, but I'd avoid programming languages that require such complex, non-universal optimizations to have usable performance in practice. Programs written in such languages may very well fail to have the same performance under a different, or future compiler.
In short:
- Some program optimizations can change the asymptotic complexity of programs, hopefully by lowering them.
- It is generally impossible to give a compiler-independent and human-understandable definition of the cases in which a particular optimization may apply.
- The domain of optimizations done by successive versions of a compiler tracking advances in compiling techniques is not necessarily monotone, and it is often impossible to guarantee that the domain of a new optimization is a "superset" of a previous one.
- Optimizations do not necessarily compose, for instance if you use a different internal representation for programs, for example by going to SSA form.
- Therefore, nothing guarantees that the optimizations that apply to a program P at compiler version n will also apply at compiler version n + 1.
- Therefore, regular use of compilers that do complicated, asymptotic-complexity-changing optimizations that are not specified in the language may lead people to write programs that will depend on the availability of those particular optimizations and that may break with future versions of the compiler.
- Lazy by default languages such as Haskell seem to require such sophisticated optimizations in order to yield acceptable performance.
- Hence one should be careful to not depend on unmandated optimizations when writing programs in such languages.
