> A lot of these suboptimal examples come down to the complexity of the optimization problem. That and the rest of what you wrote is true in a general sense, f

> A lot of these suboptimal examples come down to the complexity of the optimization problem. That and the rest of what you wrote is true in a general sense, for many examples of suboptimal code generation. I don't think it's true in the specific case of (most of) these suboptimal examples listed in the featured article. Almost all of these seem to be due to programmer oversight in formulating some rules or pattern matches, not due to heuristics for combinatorial optimization making unfortunate choices. For example, of the eight issues listed for CompCert, only the two concerning spilling and coalescing seem to be due to imperfect heuristics. A bunch of the others are simply due to pattern matches that nobody had thought (or bothered) to add, as you can see from the linked patches. No combinatorial optimization, heuristic or otherwise, going on there. Other missing pattern matches are Clang's vnmla instruction selection issue (again, there is a patch that simply adds a pattern somewhere) or the fact that it seems to lack some rules for computing the possible value range for expressions of the form "x % c" with c constant (or propagating such ranges to divisions by constants). Even for some of the examples involving registers and spilling, I don't think it's unfortunate heuristic solvers. For GCC's "float to char conversion through memory" issue, a developer stated in the bug report that the cost model is wrong, implying that fixing the costs should make the solver find the "right" code. And the GCC "spill instead of register copy" example never even touches the r2 register anywhere in the function, so it would be available for allocation by even the most primitive heuristic solver. There, too, I would suspect a bug in the model rather than an unlucky solver. So I think my point is, it's true that NP-hard problems are a curse in many subproblems of optimizing compilation, but there are many, many other possible reasons for missed optimizations.