Compilers

Hello, /prog/raiders.

I've got a question I'd like to discuss with you.

Suppose one had a compiler, interpreter or any such device, for any programming language (no matter what type or paradigm), which, given a single program, had access to the entirety of the code this program would use. In other words, the compiler would have the source code (or anything equivalent to that for that matter), of every library or system call the program would use.

That is, the entirety of the execution domain of the program is completely closed under the constraints imposed by its sole description. There would be no single side effect or transformation in the program's state which would be unknown to the compiler in advance. The compiler could evaluate the entire program flow from beginning to end, without anything outside of it interfering in the program, except, of course, the program's input (which would be handled by the compiler as such).

That is, given a program P(x) = y and an input I, the compiler could, a priori, produce the output P(I) = O completely by itself, or, equivalently, produce a constant ("hard-coded") program Q = P(I) = O which simply outputted O without any input.

Given that situation, isn't it true that the compiler would be able to produce very high quality ("optimized") machine code without relying on hints given by the programmer in order to decide a number of things?

Consider, for example, the C language. Keywords such as restrict, inline or even register serve mostly as hints for allowing the compiler to produce better code. But if the compiler had access to every piece of code in a C program -- every object definition, every branch point, every call site --, these hints, and many others, could simply be deemed unnecessary. Even things like defining an ABI could be omitted -- if a copy of every function is to be emitted in a given binary image, the compiler could decide the best calling method or convention to invoke these functions; if not, the compiler could decide the best calling method from the point of view of the callee (in a shared library, for example).

Naturally, some situations are theoretically undecidable. Nonetheless, the compiler would know all of the possibilities (which, as far as I can perceive, would depend only on the program's input), and could use this information on its favor.

Put apart whether all of this is feasible or not, is my reasoning flawed at some point?

>>1
All major C/C++ compilers already do this. It's called Whole Program Optimization. It does not and cannot work across shared-library/DLL boundaries, but it does work across static libraries during the link process.

http://en.wikipedia.org/wiki/Whole_program_optimization

In GCC land, it's called Link Time Optimization or LTO.

http://gcc.gnu.org/wiki/LinkTimeOptimization

Even FreePascal does it.

http://wiki.freepascal.org/Whole_Program_Optimization

Yep, it's basically Link-Time Optimization, Lispers also call it tree shaking.

Still, things like interacting with the world (I/O and such) can't be decided at compile-time, because the compiler can't guess all the inputs you're going to give EVER and in the order you're going to give them.
Also, think about reading from a truly random source, or reading the system clock's time. Those are going to change.

So, no, the compiler wouldn't be able to fully optimize a program unless it also knows the state of the whole universe.