Browse Prior Art Database

Fast Algorithm for Spill Code Generation in Optimizing Compilers

IP.com Disclosure Number: IPCOM000100984D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 1 page(s) / 34K

Publishing Venue

IBM

Related People

Philips, TK: AUTHOR

Abstract

Disclosed is a fast algorithm to generate spill code in an optimizing compiler. Traditionally (1,2), the choice of a spill variable has been guided by the ratio of its spill cost to its degree. It is, for example, more expensive to spill the index of the innermost loop in a series of nested loops than it is to spill the index of the outermost one. Variables are spilled in order or increasing cost degree ratio till the chromatic number of the reduced graph is less than the number of registers. This algorithm, in contrast, works by spilling nodes in order of increasing ratio of cost to clique potential (defined to be the sum of the degrees of a node and all its neighbors) till the chromatic number of the reduced graph is less than the number of registers. The clique potentials can be computed in O(¯E¯) time.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 98% of the total text.

Fast Algorithm for Spill Code Generation in Optimizing Compilers

       Disclosed is a fast algorithm to generate spill code in
an optimizing compiler.  Traditionally (1,2), the choice of a spill
variable has been guided by the ratio of its spill cost to its
degree.  It is, for example, more expensive to spill the index of the
innermost loop in a series of nested loops than it is to spill the
index of the outermost one. Variables are spilled in order or
increasing cost degree ratio till the chromatic number of the reduced
graph is less than the number of registers.  This algorithm, in
contrast, works by spilling nodes in order of increasing ratio of
cost to clique potential (defined to be the sum of the degrees of a
node and all its neighbors) till the chromatic number of the reduced
graph is less than the number of registers.  The clique potentials
can be computed in O(¯E¯) time.  Nodes of high clique potential are
likely to belong to large cliques, and removing them as early as
possible helps reduce the chromatic number of the graph.  As a
result, we expect this method to generate less spill code than other
methods with little or no sacrifice in speed.

      References
(1)  G. Chaitin, "Register Allocation and Spilling Via Graph
Coloring," Proceedings of the SIGPLAN, Symposium on Compiler
Construction, 98-105 (1982).
(2)  G. Haitin, M. Auslander, A. K. Chandra, J. Cocke, M. Hopkins,
and P. Markstein, "Register Allocation Via Coloring," Computer
Languag...