Browse Prior Art Database

Method for Spill Code Generation in Optimizing Compilers

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

Publishing Venue

IBM

Related People

Philips, TK: AUTHOR

Abstract

Disclosed is a method to reduce the amount of spill code generated by 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. Names are spilled in order of increasing cost degree ratio until the chromatic number of the reduced graph is less than the number of registers. However, no attempt is made to investigate whether or not spilling a variable will actually lead to a reduction in the number of colors needed to color the graph. It is the purpose of this disclosure to propose one such method.

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

Method for Spill Code Generation in Optimizing Compilers

       Disclosed is a method to reduce the amount of spill code
generated by 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.  Names are spilled in order of
increasing cost degree ratio until the chromatic number of the
reduced graph is less than the number of registers.  However, no
attempt is made to investigate whether or not spilling a variable
will actually lead to a reduction in the number of colors needed to
color the graph.  It is the purpose of this disclosure to propose one
such method.

      Our method is as follows: Spill names of minimal cost that are
contained in cliques of size larger than R till the reduced graph can
be colored with, at most, R colors (R is the number of hardware
registers).  If at any stage in the process, all the names are
contained in cliques of size, at most, R, spill that chain of minimum
cost whose corresponding clique is as large as possible.

      Note that it is necessary (but not sufficient) that all names
be contained in cliques of size, at most, R for the registers to be
allocatable.

      Finding the largest clique is NP-hard, but may be solved
approximately in polynomial time.  The computational requir...