Re: Graph coloring register allocation via iterative scan

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

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