Register Allocation Via Clique Separators

Global register allocation is commonly performed by constructing an interference graph and coloring it using registers. The coloring algorithms can be expensive and the size of the interference graph can become very large. In this paper we present a strategy for performing global register allocation, using graph coloring, that is both efficient in space and time. Since the algorithm is highly efficient, it eliminates the need for a local register allocation phase. The algorithm partitions a program into code segments for which the interference graphs are constructed one at a time and colored independently. The colorings for the partitions are combined to obtain an allocation for the entire code segment. The algorithm is based up on a result by Tartan regarding colorability of graphs decomposable using clique separators. The partitioning of a graph using clique separators increases the likelihood of obtaining a coloring and hence an allocation of registers for the program.