The halting problem means that for typical programs, you can't prove control flow. Proving optimization means not only proving control flow, but then knowing wh

The halting problem means that for typical programs, you can't prove control flow. Proving optimization means not only proving control flow, but then knowing which branches get taken most often so you can optimize. There may be a small subset of programs for which this is true, but the rest leave the compiler completely blinded. OoO execution does an end run around this by examining the program as it runs and adapting to the current reality rather than a simulated reality. This is the same reason a JIT can do optimizations that a compiler cannot do. The ability to look 500-700 instruction into the future to bundle them together into a kind of VLIW dynamically is a very powerful feature. As to compiler theory, it really isn't that advanced. Our "cutting edge" compilers are doing glorified find-and-replace for their final optimizations (peephole optimization). Look at SIMD and auto-vectorization. There are so many potential questions the compiler can't prove the answer to that even trivial vectorization that any programmer would identify can't be used by the compiler to the point where the entire area of research has resulted in basically zero improvements in real-world code.