6 ms·

These results don't surprise me. A lot of these suboptimal examples come down to the complexity of the optimization problem. Compilers tend to use heuristics

These results don't surprise me. A lot of these suboptimal examples come down to the complexity of the optimization problem. Compilers tend to use heuristics to come up with "generally good enough" solutions in the optimizers instead of using a longer and computationally more expensive foray into the solution space. Register allocation is a prime example. This is an NP-Hard problem. Plenty of heuristics exist for finding "generally good enough" solutions, but without exhausting the search space, it typically isn't possible to select the most optimal solution, or even to determine whether a given solution is optimal. Couple this with the tight execution times demanded for compilers, and issues like these become pretty common. Even missed strength reduction opportunities, such as eliminating unneeded spills or initialization, can come down to poor heuristics. It's possible to write better optimizer code, but this can come at the cost of execution time for the compiler. Hence, faster is often chosen over better. In first-tier platforms like ix86 and x86_64, enough examples and eyes have tweaked many of the heuristics so that "generally good enough" covers a pretty wide area. As someone who writes plenty of firmware, I can tell you that it's still pretty common to have to hand-optimize machine code in tight areas in order to get the best trade-off between size, speed, and specific timing requirements. A good firmware engineer knows when to trust the compiler and when not to. Some of this comes down to profiling, and some comes down to constraints and experience. Then, there are areas in which compilers typically rarely produce better code than humans. Crypto is one example. Crypto code written in languages like C can break in subtle ways, from opening timing oracles and other side-channel attacks to sometimes getting the wrong result when assumptions made by the developer and the optimizer are at odds. In these cases, hand-written assembler -- even in first tier platforms -- tends to be both faster and safer, if the developer knows what he/she is doing.

userbinator 9y ago
Register allocation is a prime example. This is an NP-Hard problem. Plenty of heuristics exist for finding "generally good enough" solutions, but without exhausting the search space, it typically isn't possible to select the most optimal solution, or even to determine whether a given solution is optimal. That's true only if you're not using SSA-based dataflow analysis (an idea so amazingly simple and powerful that I've often wondered why it didn't become popular sooner); otherwise, the interference graph is chordal and optimal register allocation essentially becomes a very simple linear-time algorithm. http://compilers.cs.uni-saarland.de/projects/ssara/ http://compilers.cs.uni-saarland.de/projects/ssara/ http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf
- fooker 9y ago
  The graph coloring problem for chordal graphs is tractable, true. But register allocation involves a lot more than just graph coloring. For example where and how you insert spill code makes a huge difference. Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advantages of having a chordal graph goes out of the window.
  - cwzwarich 9y ago
    > Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advantages of having a chordal graph goes out of the window. IMO, the most important insights of the work on SSA-based register allocation go beyond the idea that chordal interference graphs are easily colorable. In particular, 1) The idea that register allocation can be decoupled into separate allocation and assignment phases. Without this, you either have to view register allocation as an integrated problem, which makes it difficult to apply heuristics, or you have to have miniature register suballocators inside of different phases of your register allocator. The asymptotic horizon of the last possibility is GCC's reload. Of course, the further your architecture deviates from the theoretical model of SSA register allocation, the less you can see the benefit. In particular, estimating liveness with excessive use of subregisters is difficult, and splitting live ranges to satisfy register constraints can push the majority of the difficult problems back into copy elimination. 2) The recognition of the role of parallel copy semantics of phi pseudofunctions. Even if you were writing a conventional non-SSA register allocator, it would be wise to eliminate SSA form by introducing parallel copies and preserving those as late as possible to avoid spurious interferences. Both of these ideas are actually present in Lueh's work on fusion-based allocation (which decouples allocation by simply repeatedly checking whether graphs are still greedily k-colorable, rather than relying on chordality), but it is easier to see that in hindsight.
- bonzini 9y ago
  There is still the issue of compiling phi functions effectively, though. The result in the end is less efficient than approximate graph coloring, if I remember correctly the work you cite.
gergo_barany 9y ago
> 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.

userbinator 9y ago

Register allocation is a prime example. This is an NP-Hard problem. Plenty of heuristics exist for finding "generally good enough" solutions, but without exhausting the search space, it typically isn't possible to select the most optimal solution, or even to determine whether a given solution is optimal. That's true only if you're not using SSA-based dataflow analysis (an idea so amazingly simple and powerful that I've often wondered why it didn't become popular sooner); otherwise, the interference graph is chordal and optimal register allocation essentially becomes a very simple linear-time algorithm. http://compilers.cs.uni-saarland.de/projects/ssara/ http://compilers.cs.uni-saarland.de/projects/ssara/ http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf http://www.cs.ucla.edu/~palsberg/paper/aplas05.pdf

fooker 9y ago
The graph coloring problem for chordal graphs is tractable, true. But register allocation involves a lot more than just graph coloring. For example where and how you insert spill code makes a huge difference. Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advantages of having a chordal graph goes out of the window.
- cwzwarich 9y ago
  > Also, for SSA, you can split some variables to have smaller live ranges which are more likely to get registers. The moment you do that, the theoretical advantages of having a chordal graph goes out of the window. IMO, the most important insights of the work on SSA-based register allocation go beyond the idea that chordal interference graphs are easily colorable. In particular, 1) The idea that register allocation can be decoupled into separate allocation and assignment phases. Without this, you either have to view register allocation as an integrated problem, which makes it difficult to apply heuristics, or you have to have miniature register suballocators inside of different phases of your register allocator. The asymptotic horizon of the last possibility is GCC's reload. Of course, the further your architecture deviates from the theoretical model of SSA register allocation, the less you can see the benefit. In particular, estimating liveness with excessive use of subregisters is difficult, and splitting live ranges to satisfy register constraints can push the majority of the difficult problems back into copy elimination. 2) The recognition of the role of parallel copy semantics of phi pseudofunctions. Even if you were writing a conventional non-SSA register allocator, it would be wise to eliminate SSA form by introducing parallel copies and preserving those as late as possible to avoid spurious interferences. Both of these ideas are actually present in Lueh's work on fusion-based allocation (which decouples allocation by simply repeatedly checking whether graphs are still greedily k-colorable, rather than relying on chordality), but it is easier to see that in hindsight.
bonzini 9y ago
There is still the issue of compiling phi functions effectively, though. The result in the end is less efficient than approximate graph coloring, if I remember correctly the work you cite.

gergo_barany 9y ago

> 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.