@TechReport{	  it:2002-021,
  author	= {Johan Runeson and Sven-Olof Nystr{\"o}m},
  title		= {Generalizing Chaitin's Algorithm: Graph-Coloring Register
		  Allocation for Irregular Architectures},
  institution	= {Department of Information Technology, Uppsala University},
  department	= {Computing Science Division},
  year		= {2002},
  number	= {2002-021},
  month		= may,
  abstract	= {We consider the problem of generalizing Chaitin-style
		  graph-coloring register allocation to the irregular
		  architectures used in embedded systems. A class of formal
		  machine descriptions is introduced, capable of describing a
		  wide range of irregular architectures. We extend Chaitin's
		  register allocation algorithm to handle any architectural
		  constraints that can be expressed using these machine
		  descriptions. The generalized algorithm is applicable to a
		  wider range of architectures and systems than any other
		  adaptation of Chaitin's algorithm found in the literature.
		  We argue that the modifications to the original algorithm
		  can be combined with most important extensions to Chaitin's
		  framework, for example coalescing and optimistic coloring.
		  }
}