Re: Graph coloring when targeting IA32 processors?

Dave Boyle wrote:
> On page 123 of the third edition of 'Computer Architecture: A
> Quantitative Approach', the authors state:
>
> "Graph coloring works best when there are at least 16 (and preferably
> more) general-purpose registers available for global allocation for
> integer variables and additional registers for floating point.
> Unfortunately, graph coloring does not work very well when the number
> of registers is small because the heuristic algorithms for coloring
> the graph are likely to fail."


I think it is true. Just check the benchmarks for new gcc (color
based) register allocator for AMD64 (16 general purpose registers) and
x86 (8 general purpose registers) in Michael Matz's article "Design
and implementation of the graph colouring register allocator for GCC"


http://www.linux.org.uk/~ajh/gcc/gccsummit-2003-proceedings.pdf


> Does this mean that graph coloring is rarely (or possibly never) used
> by compilers targeting the IA32 family of processors, with their eight
> integer GPRs?


No, it does not. The colour based algorithm can work well together
with other algorithms (see for example Robert Morgan's book).

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