4 ms·

Graph coloring is a small part of register allocation, and not the hard part. It's also not NP complete on interference graphs built from SSA form, which most

Graph coloring is a small part of register allocation, and not the hard part. It's also not NP complete on interference graphs built from SSA form, which most modern compilers (though not GCC) use in the backend. In fact, it's linear time optimally solvable if you build ssi form, which can be done in linear time. The optimal spilling and rematerialization problems have not yet shown to be solvable in polynomial time on these forms, but folks are working on it.

andrewflnr 11y ago
The bit about SSI form is news to me. I have more research to do.
- DannyBee 11y ago
  See http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf Look at page 10. (Fernando was once my intern, back in the day ;P)
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.

andrewflnr 11y ago

The bit about SSI form is news to me. I have more research to do.

DannyBee 11y ago
See http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf http://web.cs.ucla.edu/~palsberg/paper/PereiraPalsberg08.pdf Look at page 10. (Fernando was once my intern, back in the day ;P)

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.