An improved method is provided for performing register allocation in a
compiler. This method determines the allocation of a plurality R of
registers of a processor for use during the execution of a software
program. The register allocation process is treated as a graph-coloring
problem, such that an interference graph is constructed for the software
program, the graph is simplified, and an R-coloring the interference
graph to the extent possible is attempted. Then, spill code is inserted
in the software program each for each uncolored node of the graph, a new
interference graph is constructed, and the process is repeated. During
the simplification process, nodes with degree greater than or equal to R
are removed from the graph in an order dictated by a spill cost metric.
During the coloring process, these same nodes are reinserted in the graph
in an order dictated by reapplying the spill cost metric.