Accession Number : ADA254554


Title :   Program Structure as a Basis for the Parallelization of Global Compiler Optimizations


Descriptive Note : Doctoral thesis


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE


Personal Author(s) : Zobel, Angelika


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254554.pdf


Report Date : 15 May 1992


Pagination or Media Count : 146


Abstract : 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.


Descriptors :   *COMPILERS , *OPTIMIZATION , *PARALLEL PROCESSING , ALLOCATIONS , COLORING , CONFLICT , COSTS , GLOBAL , GRAPHS , INTERACTIONS , LOOPS , MODELS , ORGANIZATIONS , SEPARATORS , STRUCTURES


Subject Categories : Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE