Program structure as basis for parallelizing global register allocation

A model that uses knowledge about program structure to guide global register allocation explicitly is proposed. Restrictions that must be met by the live ranges of loops and conditionals such that the corresponding portion of the register conflict graph is an interval graph are defined. Interval graphs are desirable because they can be colored optimally in polynomial time and because clique separators can be located systematically in interval graphs. Clique separated components of the conflict graph can be colored individually and recombined to an overall coloring, a platform for parallel global register allocation. The method has been implemented and results are presented for a benchmark of C kernels. It was possible to map most conflict graphs of the benchmark to an equivalent interval graph. In each conflict graph, it was possible to identify a large number of clique separators; the parallelization of global register allocation is then straightforward