Re: Graph coloring register allocation via iterative scan

Ulrich Hobelmann <u.hobelmann@web.de>
24 Feb 2006 09:37:46 -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)
Re: Graph coloring register allocation via iterative scan koes@cmu.edu (dkoes) (2006-03-11)
| List of all articles for this month |

From: Ulrich Hobelmann <u.hobelmann@web.de>
Newsgroups: comp.theory,comp.compilers,comp.programming
Followup-To: comp.compilers
Date: 24 Feb 2006 09:37:46 -0500
Organization: Compilers Central
References: 06-02-018 06-02-115 06-02-152
Keywords: registers, code
Posted-Date: 24 Feb 2006 09:37:46 EST

(Followup-to: comp.compilers)


Sid Touati wrote:
> Completely agreed, the linear scan register allocation didn't bring
> anything new from the computer science perspective, and any person
> aware about graph theory knows this.
>
> Since many people working on code optimization are mainly interested in
> computer engineering aspects, the linear scan register allocation seems
> a new method to them, which is not really the case.


Hm, maybe it is so. I personally don't like graph coloring too much,
for one reason: it's only about variables having a single lifetime, in
one single place, which is totally unrealistic.


Variables may have ranges of lifetimes (though transformation to
something like SSA can probably split those lifetimes pretty well), and
most importantly they aren't places, but values, i.e. a variables is
*needed* in certain places, like in a certain register as a function
argument, or a return value, or in ANY register to serve as another value.


Graph RAs seem to solve this by inserting moves, but I'd rather have a
backwards working RA that loads values on demand, maybe a few cycles in
advance so it's good for the pipeline. I don't see where a global graph
coloring, that merely assigns variables to locations in a static way,
can do that.


Please correct me if I'm mistaken.


--
Suffering from Gates-induced brain leakage...


Post a followup to this message

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