Re: Graph coloring register allocation via iterative scan

"Rob Thorpe" <robert.thorpe@antenova.com>
6 Feb 2006 00:08:07 -0500

          From comp.compilers

Related articles
Graph coloring register allocation via iterative scan avayvod@gmail.com (2006-02-03)
Re: Graph coloring register allocation via iterative scan robert.thorpe@antenova.com (Rob Thorpe) (2006-02-06)
Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-07)
Re: Graph coloring register allocation via iterative scan avayvod@gmail.com (Whywhat) (2006-02-11)
Re: Graph coloring register allocation via iterative scan vmakarov@redhat.com (Vladimir Makarov) (2006-02-14)
Re: Graph coloring register allocation via iterative scan sylerugby@yahoo.com (2006-02-17)
Re: Graph coloring register allocation via iterative scan Sid.Touati@inria.fr (Sid Touati) (2006-02-20)
Re: Graph coloring register allocation via iterative scan u.hobelmann@web.de (Ulrich Hobelmann) (2006-02-24)
[1 later articles]
| List of all articles for this month |

From: "Rob Thorpe" <robert.thorpe@antenova.com>
Newsgroups: comp.theory,comp.compilers,comp.programming
Date: 6 Feb 2006 00:08:07 -0500
Organization: http://groups.google.com
References: 06-02-018
Keywords: registers

avayvod@gmail.com wrote:
> I wonder whether register allocation via graph coloring (improved by
> Preston Briggs) is commonly better than iterative scan algortihm
> (introduced by Alkis Evlogimenos). In what cases one is better than
> the other? Are there some theoretical proofs of dominance of one of
> the methods?
>
> By being better I mean producing more efficient code with less register
> spills.


Register allocation algorithms can be complicated. As important as
good code is producing something that allocates fast enough not to
hurt compile times too much, this was the intention of linear scan.


It also can be very difficult to bolt a particular algorithm into a
particular compiler. A while ago an attempt was made to put a Briggs
like allocator into GCC, but GCC's backend had a completely different
point of view of the machine making it very complex. The authors
ended up writing something like 16Kloc to do something that in so
compilers only takes ~1Kloc, and in the end gave up. So GCC still
uses something else (an odd variation of the Chow/Hennessey algorithm
I think).


Post a followup to this message

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