Re: Graph coloring when targeting IA32 processors?

Vladimir Makarov <>
5 Jun 2003 23:15:24 -0400

          From comp.compilers

Related articles
Graph coloring when targeting IA32 processors? (2003-06-03)
Re: Graph coloring when targeting IA32 processors? (2003-06-05)
Re: Graph coloring when targeting IA32 processors? (Vladimir Makarov) (2003-06-05)
| List of all articles for this month |

From: Vladimir Makarov <>
Newsgroups: comp.compilers
Date: 5 Jun 2003 23:15:24 -0400
Organization: Red Hat, Inc.
References: 03-06-027
Keywords: 386, optimize, registers
Posted-Date: 05 Jun 2003 23:15:23 EDT

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"

> 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).

Post a followup to this message

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