Graph colouring with unlimited colours

G'day all.


I'm interested in references for graph colouring where the maximum
number of colours is in general unbounded (but should be as small as
possible). I need this for a virtual machine where thousands of
instances of a given program may be running at any given time, so
using one less register may save a lot of memory (which is in short
supply in this particular application).


The simplest algorithm is to repeatedly remove the smallest degree
node and assign it the smallest colour possible (inventing a new
colour if necessary). However, this doesn't in general do as well as
delayed colouring.


Has anyone done any work on how badly the "assign a colour to the
smallest degree node" algorithm works in the average/worst case
compared with "optimal" colouring? Or has anyone tried some sort of
delayed colouring algorithm where the number of colours is not fixed
beforehand?


I'm also considering a hybrid approach where you choose a "reasonable"
number of colours, colour with spilling, then repeat the algorithm on
the spilled nodes. Has anyone tried this? How well does it work in
the average/worst case?


Oh, and also, if anyone has any good coalescing heuristics which don't
depend on choosing a number of colours beforehand, that would be
extremely helpful too.


Thanks in advance, etc.


Cheers,
Andrew Bromage

Return to the comp.compilers page.
Search the comp.compilers archives again.