Path: utzoo!attcan!uunet!lll-winken!lll-lcc!ames!mailrus!cwjcc!tut.cis.ohio-state.edu!rutgers!aramis.rutgers.edu!klaatu.rutgers.edu!josh
From: josh@klaatu.rutgers.edu (J Storrs Hall)
Newsgroups: comp.arch
Subject: Re: Vertex coloring and register allocation
Message-ID: <Jan.16.14.09.52.1989.18225@klaatu.rutgers.edu>
Date: 16 Jan 89 19:09:57 GMT
References: <5072@itsgw.RPI.EDU>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 18


	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