Re:RTX2010 – Radiation-hardened stack machine microprocessor
by CHY872 on Saturday November 15, 2014 @02:20PM
(#8612383)
Ok, 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