Journal article
Using graph coloring in an algebraic compiler
Acta informatica, Vol.34(3), pp.191-209
03/03/1997
DOI: 10.1007/s002360050079
Abstract
An algebraic compiler allows incremental development of the source program and builds its target image by composing the target images of the program components. In this paper we describe the general structure of an algebraic compiler focusing on compositional code generation. We show that the mathematical model for register management by an algebraic compiler is a graph coloring problem in which an optimally colored graph is obtained by composing optimally colored subgraphs. More precisely, we define the clique-composition of graphs G1 and G2 as the graph obtained by joining all the vertices in a clique in G1 with all the vertices in a clique in G2 and show that optimal register management by an algebraic compiler is achieved by performing clique-composition operations. Thus, an algebraic compiler provides automatically adequate clique separation of the global register management graph. We present a linear-time algorithm that takes as input optimally colored graphs G1 and G2 and constructs an optimal coloring of any clique-composition of G1 and G2. Motivated by the operation of clique-composition, we define the class of clique-composable graphs as those graphs that can be iteratively built from single vertices using the clique-composition operation. We show that the class of clique-composable graphs coincides with the well-known class of chordal graphs.
Details
- Title: Subtitle
- Using graph coloring in an algebraic compiler
- Creators
- Teodor Rus - University of IowaSriram Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Acta informatica, Vol.34(3), pp.191-209
- DOI
- 10.1007/s002360050079
- ISSN
- 0001-5903
- eISSN
- 1432-0525
- Language
- English
- Date published
- 03/03/1997
- Academic Unit
- Computer Science
- Record Identifier
- 9984259474302771
Metrics
10 Record Views