spencert@itsgw.RPI.EDU (Thomas Spencer) (01/15/89)
I rember reading in this group that vertex coloring is useful when doing register allocation. Would someone mail me a reference to a paper that describes the connection, or better yet, post a brief explaination. Thank you. -- -Tom Spencer spencert@turing.cs.rpi.edu uunet!steinmetz!itsgw!spencert "First figure out what you are trying to do." -Me.
josh@klaatu.rutgers.edu (J Storrs Hall) (01/17/89)
I rember reading in this group that vertex coloring is
useful when doing register allocation. Would someone
... post a brief explaination.
-Tom Spencer
Well, this doesn't have a lot to do with architecture, but basically
you build a graph with a vertex for each variable. There is an edge
between vertices which are in use at the same time. Now color the
graph; you'll need one register per color. Commonly, you might have
k registers so you try to k-color the graph, and emit spill code
to break variables until you can.
("Variable", by the way, doesn't strictly correspond to a source
code variable. It is more like "an edge in the dataflow graph of
the program".)
--JoSH