EFFICIENT REGISTER ALLOCATION VIA COLORING USING CLIQUE SEPARATORS

Although graph coloring is widely recognized as an effective technique for register allocation, memory demands can become quite high for lar ge interference graphs that are needed in coloring. In this paper we p resent an algorithm that uses the notion of clique separators to impro ve the space overhead of coloring. The algorithm, based on a result by R. Tarjan regarding the colorability of graphs, partitions program co de into code segments using clique separators. The interference graphs for the code partitions are constructed one at a time and colored ind ependently. The colorings for the partitions are combined to obtain a register allocation for the entire program. This approach can be used to perform register allocation in a space-efficient manner. For straig ht-line code (e.g., local register allocation), an optimal allocation can be obtained from optimal allocations for individual code partition s. Experimental results are presented demonstrating memory demand redu ctions for interference graphs when allocating registers using clique separators.