Program structure as a basis for the parallelization of global compiler optimizations
Angelika Zobel · 1992
Optimizing compilers can produce very efficient code but incur a high compilation cost. Because interactions between arbitrary points in a program are possible, global compiler optimizations are inherently expensive and in general there is no easy way to partition the data processed during global compiler optimizations into independent components. This thesis explores how program structure can be used to provide a basis for the parallelization for global compiler optimizations. Two concepts to obtain data parallelism in global compiler optimizations are described. The first concept uses program structure explicitly for the parallelization, demonstrated by the parallelization of interval analysis of global data flow equations. The second concept consists of using program structure analytically to establish data partitioning points. The effectiveness of this concept is demonstrated in the parallelization of global register allocation via optimal coloring of a graph denoting register conflicts, an NP complete problem. A model for global register allocation in which program structure is used to analyze a register conflict graph is presented. The purpose of this analysis is to detect clique separators that partition a conflict graph into independent components that can be colored independently and combined to an overall coloring by renaming. Properties of live ranges in loops and conditionals are linked to characteristics of the conflict graph. If certain restrictions are met by the live ranges that occur in conditionals and loops, the register conflict graph can be transformed to an equivalent interval graph. Interval register conflict graphs are desirable because they can be colored optimally in polynomial time and because all clique separators of an interval graph can be located systematically. The experimental evaluation of my method shows that in many cases the entire conflict graph or large portions thereof can be mapped to equivalent interval graphs. Consequently, in such conflict graphs almost all clique separators can be detected which makes it easy to partition the conflict graph into components that can be processed independently. The knowledge about interval portions of register conflict graph can be used both as a platform for the parallelization of global register allocation and to improve sequential register coloring algorithms.