\documentstyle[11pt,fullpage]{article}

\begin{document}

\begin{center}
{\Large \bf Coloring Sparse Weighted Graphs}\\
{\large \bf (Preliminary Abstract)}\\
Russell W. Quong\\
Electrical Engineering\\
Purdue University\\
W. Lafayette, IN 47907-1285\\
quong@ecn.purdue.edu\\
25 January, 1993\\
\end{center}

{\bf Classification}:  Optimization problem:  Coloring weighted
graphs that arise from register allocation in an optimizing
compiler.  Empirical and theoretical work.

\section{Introduction}

This work involves coloring graphs obtained from performing
register allocation in an optimizing compiler.  The use of graph
coloring is well known \cite{Bernstein89} \cite{Briggs89}
\cite{ChowHennessy90} \cite{Gupta89} \cite{Larus86}
\cite{Callahan91}.  The {\em graph coloring decision problem} $GC$
asks ``Given an undirected unweighted graph $G$, is it possible to
color the vertices of $G$ using $\le k$ colors such that no edge
connects two vertices of the same color?''  In register
allocation, each vertex of the {\em interference graph} $G$
represents definitions and uses of a variable.  A color represents
a physical register.  Two vertices $u$ and $v$ in $G$ have an edge
if their corresponding variables are live simultaneously, because
if both $u$ and $v$ are assigned to the same register, they will
``interfere'' with each other.  A {\em spill\/} occurs when a
variable must be moved between memory and registers.

We question whether coloring an {\em unweighted} interference
graph (UIG) is a good model for register allocation.  Instead, we
recommend the use of a {\em weighted} interference graph (WIG)
that has both edge and vertex weights.  A notable difference, is
that a vertex can remain {\em uncolored\/}, in which case it does
not incur its vertex weight or its adjacent edge weights.  The
cost of edge $(u,v)$ is incurred if $u$ and $v$ are colored with
the same color.  The cost of vertex $v$ is incurred if $v$ is
colored with any color.  The weighted graph coloring
(optimization) problem is ``Given WIG $G$, what is the coloring of
$G$ with the smallest total cost?''

A WIG vertex represents an arbitrary subset of the sites (uses and
definitions) of a variable.  All weights are scaled by the
frequency of execution.  A negative weight represents the relative
savings of keeping a variable in a register versus memory.  As
fully described in \cite{QuongChen92}, a WIG has both positive and
negative edges but vertex weights are always negative.  Most edges
are positive.  There is a substructure to the graph, partitioning
the graph into regions (basic blocks).  Some regions are heavily
weighted; others are not.

\section{Structure of Interference Graphs}

One question to be answered is ``what sort of graph arise in
register allocation work?''  It is known that interference graphs
are somewhat sparse.  How sparse, in practice are they?  (We guess
for $G = (V,E)$, we have $m$ $\approx$ $o(n\sqrt{n})$, where
$n=|V|$ and $m=|E|$, but this obviously needs further
measurement).

In practice, the use of a weighted interference graph make this
problem more an optimization problem than a decision problem (e.g.
travelling salesman is optimization, Hamilton cycle is decision).
We are looking for fast practical algorithms to color 

\section{Current Work}

We are in the process of developing tools to extract WIGs from
existing code.  We are also exploring various randomized
algorithms to color WIGs.  In particular, we are adapting the
heuristic used by Lin \cite{Lin} on the travelling salesman
problem.  More theoretical work is of interest, too, but is not
our main priority.

\newcommand{\etalchar}[1]{$^{#1}$}
\begin{thebibliography}{BGG{\etalchar{+}}89}

\bibitem[BCKT89]{Briggs89}
Preston Briggs, Keith Cooper, Ken Kennedy, and Linda Torczon.
\newblock Coloring heuristics for register allocation.
\newblock In {\em ACM SIGPLAN Conference on Programming Language Design and
  Implementation}, pages 275--284, Portland, OR, June 21--23 1989. ACM.

\bibitem[BGG{\etalchar{+}}89]{Bernstein89}
D.~Bernstein, D.~Q. Golden, M.~C. Golumbic, H.~Krawczyk, Y.~Mansour,
  I.~Nahshon, and Pinter~R. Y.
\newblock Spill code minimization techniques for optimizing compilers.
\newblock In {\em ACM SIGPLAN Conference on Programming Language Design and
  Implementation}, pages 258--263, Portland, OR, June 21--23 1989. ACM.

\bibitem[CH90]{ChowHennessy90}
Fredric Chow and John Hennessy.
\newblock The priority-based coloring approach to register allocation.
\newblock {\em ACM Transactions on Programming Languages and Systems},
  12:501--536, October 1990.

\bibitem[CK91]{Callahan91}
David Callahan and Brian Koblenz.
\newblock Register allocation via hierarchical graph coloring.
\newblock In {\em ACM SIGPLAN Conference on Programming Language Design and
  Implementation}, pages 192--203, Toronto, Canada, June 26--28 1991. ACM.

\bibitem[GSS89]{Gupta89}
Rajiv Gupta, Mary~Lou Soffa, and Tim Steele.
\newblock Register allocation via clique separators.
\newblock In {\em ACM SIGPLAN Conference on Programming Language Design and
  Implementation}, pages 264--274, Portland, OR, June 21--23 1989. ACM.

\bibitem[LH86]{Larus86}
James~R. Larus and Paul~N. Hilfinger.
\newblock Register allocation in the spur lisp compiler.
\newblock In {\em Proceedings 1986 Symposium on Compiler Construction}, pages
  255--263, Palo Alto, CA, June 1986. ACM.

\bibitem[Lin65]{Lin}
S.~Lin.
\newblock Computer solutions to the traveling salesman problem.
\newblock {\em BSTJ}, 44(10):2245--2269, 1965.

\bibitem[QC]{QuongChen92}
Russell~W. Quong and Shu-Ching~Chen Chen.
\newblock Register allocation via weighted graph coloring.
\newblock working paper.

\end{thebibliography}

\end{document}