Program Structure as a Basis for the Parallelization of Global Compiler Optimizations
CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE
Pagination or Media Count:
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 organizations 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 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.
- Computer Programming and Software