Register allocation & spilling via graph coloring

TLDR

Graph coloring has been used for global register allocation, but when the conflict graph cannot be colored with the available registers, spill code must be inserted, often resulting in suboptimal quality and high compile time. The authors aim to extend graph coloring so that it naturally solves the spilling problem. Spill decisions are based on the conflict graph and cost estimates of keeping a value in a register versus memory. This approach yields better object code and significantly reduces compile time.

Abstract

In a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental PL/I optimizing compiler. When the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. Previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. We have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. Spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. This new approach produces better object code and takes much less compile time.