3 ms·
Interesting. I agree with your statement regarding it being an NP-complete problem, as intuitively it seems that way, but do you have a reference by chance?
by s800 12y ago
Interesting. I agree with your statement regarding it being an NP-complete problem, as intuitively it seems that way, but do you have a reference by chance? Thanks!
- jlarocco 12y agoI can't find the original paper, but this almost seems more relevant. http://research.ihost.com/lcpc06/final/7/7_Paper.pdf http://research.ihost.com/lcpc06/final/7/7_Paper.pdf Actually, here's the original for sale, but the abstract doesn't explicitly mention being NP-complete. http://www.sciencedirect.com/science/article/pii/0096055181900485 http://www.sciencedirect.com/science/article/pii/00960551819...
- CHY872 12y agoOk, so we can view register allocation as being a case of graph colouring; create a graph where the nodes are your 'virtual registers' and there's an edge between two nodes if those registers are both live at the same time. Then we can run on n registers iff we can colour the graph with n colours. This is one of the first identified NP-complete problems. https://en.wikipedia.org/wiki/Graph_coloring https://en.wikipedia.org/wiki/Graph_coloring