In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff.
Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.
Totally. The hard part isn't coloring (you can use simple heuristics to get a decent register assignment), rather, it's figuring out which registers to spill (don't spill registers in hot loops! and a million other things!).
In case you haven't looked at the article, this is looking specifically at the Edge Coloring problem and not the more commonly known Vertex Coloring problem. Vertex Coloring is NP-complete unfortunately.
You can convert edge coloring problems into vertex coloring problems and vice versa through a simple O(n) procedure.
Wrong. You can convert edge-coloring problems into vertex-coloring problems of the so-called line graph: https://en.m.wikipedia.org/wiki/Line_graph
But the opposite is not true, because not every graph is a line graph of some other graph.
Hrm... right. It's been a while. And it looks like both Vertex Coloring and Edge Coloring are both NP-complete (because of the O(n) procedure you're talking about and the ability to reduce both problems down to 3-SAT). I've started looking closer at the actual paper to try to figure out what's going on here. Thanks for the reminder, I miss getting to regularly work on this stuff.
Edit: thanks sibling reply for pointing out that it's not a bidirectional transform.
2 replies →
Is this going to lead to faster compile times? Faster register allocation...
No.
In SSA, the graphs are chordal, so were already easily colorable (relatively).
Outside of SSA, this is not true, but the coloring is still not the hard part, it's the easy part.
Very few compilers actually use vertex coloring for register allocation
Totally. The hard part isn't coloring (you can use simple heuristics to get a decent register assignment), rather, it's figuring out which registers to spill (don't spill registers in hot loops! and a million other things!).
and this post isn't even about vertex coloring