4 ms·
Also, something being NP complete does not say much about whether it is hard to do in the real world. Exponential is fine, as long as the constant, the value of
by Someone 11y ago
Also, something being NP complete does not say much about whether it is hard to do in the real world. Exponential is fine, as long as the constant, the value of n, or the exponent aren't too large.
Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across.
It would be interesting (and quite an accomplishment, even if doesn't give significant performance gains) to combine this with whole-program optimization (imagine optimizing the calling conventions on a per-function basis, and considering generating code for a function twice, with different calling conventions) and/or with the code that decides what functions to inline, but AFAIK, nobody does that.
- DannyBee 11y ago"Here, real world cases likely will have only a fairly limited number of registers and only a limited (but potentially very long) length of code to optimize across. " You can do a good job with polynomial time heuristics (chaitin's heuristic) for coloring, however, you are wrong about the code. It is often very weird. At the same time, most of the performance issue is not coloring, or trying not to spill at all. The problem is deciding where to split live ranges (which introduces copies), where to merge existing live ranges (which removes copies at a cost of more interferences), where to spill, where to remat, are quite hard.