PROGRAM STRUCTURE AS BASIS FOR THE PARALLELIZATION OF GLOBAL REGISTERALLOCATION

We propose a model for global register allocation via graph coloring t hat uses knowledge about program structure to guide global register al location. We define restrictions that must be met by the live ranges o f loops and conditionals such that the corresponding portions of the r egister conflict graph are interval graphs. This knowledge is used to locate clique separators in register conflict graphs. We discuss how c lique separators can be used both to improve sequential register alloc ation and as a a platform for parallelized global register allocation. We conclude this paper by presenting measurements for a benchmark of C kernels for most of which our method found all clique separators.