Generalizing Chaitin's Algorithm: Graph-Coloring Register Allocation for Irregular Architectures

Johan Runeson and Sven-Olof Nyström

May 2002

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.

Available as PDF (234 kB, no cover)

Download BibTeX entry.