Re: Graph Coloring and Register Allocation

Robert Sherry wrote:


> I am currently developing a new graph coloring algorithm which I
> believe is well suited for use in compilers. These graphs come up in
> the register allocation problem. I believe that these graphs tend to
> have a lot of vertices of high degree (nearly n where n is the number
> of vertices in the graph), as well vertices with very low degrees. I
> believe this is true because most variables will be live throughout
> the subroutine ( or block ) and compiler generated temporaries will
> have a very short life. I am looking for a Journal article that
> states this is the case.


Depending on what you mean by compiler generated temporaries. If you
are referring to the ones used by expression evaluation, then they are
typically handled in the local register allocator, in a stack fashion,
and more expensive register allocation technique is not needed. If you
are referring to the CS etc., then their lifetimes are probably all
over the places, just like the user declared variables. Also remember
that you can split the lifetime of the variables so the effect of long
lived variables may be reduced.


--
// richard
http://www.imagecraft.com

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