That would indeed be very neat. I think it's also impossible to do in a reasonable way, because how well a compiler does is probably dependent in a huge way on the particular program. There is a huge class of program transformations that are technically correct but far too specific to implement in a general-purpose compiler, and I think how well a compiler does is mostly dependent on how many of those transformations happen to apply to your program at hand.
For example: suppose you have a program that renders a 3D scene from a hardcoded scene description. A compiler might do a lot of stuff to that program, but what it will certainly not do is notice that the whole hardcoded scene can be replaced with a small representation in the form of a distance estimation function, if the rendering algorithm is also changed from raytracing to distance estimation.
A human in a demo scene situation will certainly perform (or at least try to perform) that transformation, if only because distance estimation is well known to often provide compact representations of certain, a priori very complex, scenes.
Also, nitpick:
> Clearly this problem is NP-complete as hell
I think it's almost certainly not even in NP; that would require a polynomial algorithm that, given some evidence that you can choose, proves that a particular program really is optimal. I think that's still impossible (but am gladly proven wrong). If I'm correct, it's not NP-complete, it's NP-hard.
> how well a compiler does is mostly dependent on how many of those transformations happen to apply to your program at hand
Right, there's an infinite number of distinct useful code optimizations, there's a cost to checking if any given optimization can be applied, and some optimizations have _massive_ costs for very rare and specific savings, so any given compiler is making a practical decision to include some optimizations and omit others. There was some discussion in the Rust community about LLVM having a period where they weren't tracking regressions in compile times - so "the perfect optimizing compiler" isn't really a coherent goal. But I still wonder how much faster Optimal Chromium would be. Just another interesting number I'll never know, I suppose.
> I think it's almost certainly not even in NP
Yeah, that was sloppy of me, I think this is undecidable by Rice's theorem. Nice catch!
For example: suppose you have a program that renders a 3D scene from a hardcoded scene description. A compiler might do a lot of stuff to that program, but what it will certainly not do is notice that the whole hardcoded scene can be replaced with a small representation in the form of a distance estimation function, if the rendering algorithm is also changed from raytracing to distance estimation.
A human in a demo scene situation will certainly perform (or at least try to perform) that transformation, if only because distance estimation is well known to often provide compact representations of certain, a priori very complex, scenes.
Also, nitpick:
> Clearly this problem is NP-complete as hell
I think it's almost certainly not even in NP; that would require a polynomial algorithm that, given some evidence that you can choose, proves that a particular program really is optimal. I think that's still impossible (but am gladly proven wrong). If I'm correct, it's not NP-complete, it's NP-hard.