The K-graph coloring problem for register allocation is NP-complete, but in SSA form is actually linear. The tougher problem isn't the coloring but rather where to optimally place spills and fills around loops and calls.

https://llvm.org/devmtg/2011-11/Olesen_RegisterAllocation.pd...

Yeah, the number of "registers" needed isn't really NP-complete the way that the number of colors in a graph is. It's just the maximum number of live values, which, while not exactly trivial, is not that hard to figure out.

It would be interesting to revisit a world where languages/compilers were built explicitly with common memory access semantics/out of order op/etc in mind.

One of the things that really excites me about Rust is that it's single mutable reference enforcement means you can run run `restrict` 100% of the time if you wanted which is a non-trivial performance boost. I think it's not enabled today but from previous discussions it sounds like that's just a matter of plumbing through the right things to LLVM.

Every time I've seen that rolled out in a C/C++ codebase someone invariably forgets about pointer aliasing and you spend a week tracking down some non-deterministic behavior.

My point was that since optimization is also possible in assembly, and since assembly is considered low-level, then optimization per se shouldn't be used as something that characterize high-level languages exclusively. But it is true that some abstractions used by high-level languages enable quite complex optimization techniques, so there is a clear correlation between the level of a language and the ability of its compiler to analyze and optimize programs.